LeetCode刷题总结（1）--栈、队列、堆

队列:先进先出

栈:先进后出

堆(优先队列 ): 逻辑结构上是完全二叉树结构，其中每个字数的最大值(最小值)节点是头节点。实际结构常用数组实现。 建立一个大根堆 时间复杂度O(n)

基础题

1.数组实现栈、队列 ； 实现堆排序

  • 栈
class ArrayStack{
    int maxSize;
    int top;
    int []stack;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        top=-1;
        stack=new int[maxSize];
    }
    //栈空
    public boolean isEmpty(){
        return top==-1;
    }
    //栈满
    public boolean isFull(){
        return top==maxSize-1;
    }
    //入栈
    public void push(int i){
        if(isFull()) {
            System.out.println("栈已满");
            return;
        }
        stack[++top]=i;
    }
    //出栈
    public int pop(){
        if(isEmpty()){
           throw new RuntimeException("栈空");
        }
        int val=stack[top];
        top--;
        return val;
    }
    //显示栈顶元素，不出栈
    public int showPop(){
        if(isEmpty()){
            throw new RuntimeException("栈空");
        }
        return stack[top];
    }
    //遍历
    public void show(){
        if(isEmpty()){
            System.out.println("栈空");
            return;
        }
        for (int i = 0; i <=top; i++) {
            System.out.printf("stack[%d]=%d   \n",i,stack[i]);
        }

    }
  • 队列
class ArrayCircleQueue {
    private int maxSize;
    private int front; //指向队头
    private int rear; //指向队尾的后一个位置,且rear后预留一个位置，方便判断队空
    private int []circleArr;

    public ArrayCircleQueue(int maxSize) {
        this.maxSize = maxSize;    //因为预留一个位置，实际上只有maxSize-1个数有效
        front=0;
        rear=0;
        circleArr=new int[maxSize];
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getFront() {
        return front;
    }

    public int getRear() {
        return rear;
    }

    //判断队空
    public boolean isEmpty(){
        return rear==front;
    }
    //判断队满
    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }
    //入队
    public void enqueue(int i){
        if(isFull()){
            System.out.println("队列已满，不能添加数据");
            return;
        }
        circleArr[rear]=i;
        rear=(rear+1)%maxSize;
    }
    //出队
    public int dequeue(){
        if(isEmpty()){
            return -1;
        }
        int temp=front;
        front=(front+1)%maxSize;
        return circleArr[temp];
    }
}
  • 堆
//给定数组  建立大根堆
public static void main(String[] args){
   int[] a={.......};
   int len=a.length;
    //建立大根堆
   for(int i=len/2-1 ; i>=0; i--){
       heapSort(a,i,len);
   }
   for(int i=len-1;i>0;i--){
       int temp=a[i];
       a[i]=a[0];
       a[0]=a[i];
       heapSort(a,0,i);
   }
}
public int[] heapSort(int[] a,int i, int len){
    int temp=a[i];
    for(int j=2*i+1 ; j<len;j=2*j+1){
        if(j+1<len && a[j]<a[j+1]) j++;
        if(a[j]>temp){
            a[i]=a[j];
            i=j;
        }else break;
    }
    a[i]=temp;
}

2.用栈实现队列 ； 用队列实现栈

//栈实现队列
class MyQueue {

Stack<Integer> res = new Stack<>();
public MyQueue() {}
   
public void push(int x) {
    Stack<Integer> temp = new Stack<>();
    while(!res.isEmpty()) temp.push(res.pop());
    temp.push(x);
    while(!temp.isEmpty()) res.push(temp.pop());
}

public int pop() {
    return res.pop();
}

public int peek() {
    return res.peek();
}

public boolean empty() {
    return res.isEmpty();
}

//队列实现栈
同样准备两个队列
class MyStack {
    Queue<Integer> res = new LinkedList<>();
    }   
   
    public void push(int x) {
        Queue<Integer> temp=new LinkedList<>();
        temp.add(x);
        while(res.peek()!=null) temp.add(res.poll());
        while(temp.peek()!=null) res.add(temp.poll());
    }
    
    
    public int pop() {
        return res.poll();
    }
    
    public int top() {
        return res.peek();
    }
    
    public boolean empty() {
        return res.peek()==null;
    }
}

3.实现一个特殊的栈，在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

//另外定义一个最小栈  min_stack
class GetMinStack{
    public GetMinStack{
        
    }
    public void push(int x){
        if(min_stack.isEmpty() || x<min_stack.peek() ){
           min_stack.push(x);
         }else min_stack.push(min_stack.peek());
        stack.push(x);
    }
    public int pop(){
        min_stack.pop();
        return stack.pop(); 
    }
    public int getMin(){
        return min_stack.peek();
    }
}

4.验证栈序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 ==栈中元素不重复==

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int r = 0;
    for(int i = 0 ; i < pushed.length ; i++){
        stack.push(pushed[i]);
        while(!stack.isEmpty() && stack.peek() == popped[r]){
              stack.pop();
              r++;
          }    
     } 
    return stack.isEmpty();
}

5.有一个整数数组，找出数组中第K大的数。
要找第K大的数，需要维持一个大小为K的小根堆 ， 遍历结束结果就是小根堆的堆顶。
对于为什么是小根堆 ，如果遍历的数比堆顶小 ，那肯定其他数都小 ，如果比堆顶大，就替换堆顶，重新维持小根堆

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        int[] heap = new int[K];
        for(int i = 0 ; i < K ; i++) heap[i] = a[i];
        for(int i = K/2 - 1 ; i >= 0 ; i--) heapSort(heap,i);
        for(int i = K ; i < a.length ; i++){
            if(a[i] > heap[0]) heap[0] = a[i];
            heapSort(heap,0);
        }
        return heap[0];
    }
    public void heapSort(int[] heap , int i){
        int temp = heap[i];
        for(int j = 2*i + 1 ; j < heap.length ; j = 2*j + 1){
            if(j+1 < heap.length && heap[j] > heap[j+1]) j++;
            if(heap[j] < temp){
                heap[i] = heap[j];
                i = j;
            }else break;
        }
        heap[i] = temp;
    }
}

进阶

1.一个栈一次压入1,2,3,4,5， 将这个栈中元素逆序，即输出1、2、3、4、5，仅用递归实现，不用其他数据结构
! 递归的本质就是栈

public int getStackBottom(Stack<Integer> stack){
    int res=stack.pop();
    if(stack.isEmpty()) return res;
    int last=getStackBottom(stack);
    stack.push(res);
    return last;
}
public void reverse(Stack<Integer> stack){
    if(stack.isEmpty()) return;
    int bot=getStackBottom(stack);
    reverse(stack);
    stack.push(bot);
}

2.更新滑动窗口 最大值 最小值问题

! 双端队列 队列存放数组元素的下标

以更新最大值为例

1.对于从右侧窗口新进入的数a ，不断从双端队列的队尾释放小于等于 a 的数，直到遇到一个大于a的数或者队列为空时 ， 把 a 从双端队列的队尾放入

2.对于左侧窗口的数字b ，判断下标是否属于滑动窗口内 ， 如果不是则弹出

3.这样就保证队头是该滑动窗口的最大值

给定一个数组nums ,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。返回滑动窗口最大值

    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> list = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        int j = 0;
        for(int i = 0 ; i < nums.length ; i++){
            while(!list.isEmpty() && nums[list.getLast()] < nums[i]){
                list.removeLast();
            }
            list.addLast(i);
            if(list.getFirst() == i-k) list.removeFirst();
            if(i >= k-1) res[j++] = nums[list.getFirst()];
        }
        return res;
    }

3.单调栈

单调栈可以用来找 一个数组中 左边离他最近比他大(小)的数 和 右边离他最近比他大(小)的数

如果找 大数 就是单调递减栈 遍历数组 遇到比栈顶小的元素 直接入栈， 遇到比栈顶大的元素，栈顶出栈

新栈顶就是左边离他最近比他大的数 ，要 push的数就是右边离他最近比他大的数

3.a给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积

LeetCode84.png
// 对于每个柱子   往两边扩散 直到遇到比它小的柱子  就求出以这个柱子为中心的矩形面积
// 以某个柱子 i 为中心 ，也就是生成的矩形高为 heights[i]
// 利用单调递增栈 求出 每个柱子 左边最近比它小的柱子  和 右边 最近比它小的柱子
// 每次某个元素出栈的时候 ，要入栈的元素就是它右边最近比它小的元素 ， 出栈后的栈顶(新元素还没入栈)就是它左边最近比它小的元素 ，如果出栈后栈为空， 那么就是说这个元素左边没有比它小的元素，可以定义左边比它小的元素下标为-1
// 对于 相等的元素，一样进行出栈 ，因为即使前一个相等的元素提前出栈，以它为中心生成的最大矩形 一定 被后一个相等元素生成的矩形囊括
public int getMaxRect(int[] heights){
    Stack<Integer> stack = new Stack<Integer> stack;  //栈中存放的是柱子的下标
    int maxSize=0;
    for(int i=0;i<heights.length;i++){
        while(!stack.isEmpty() && heights[i] <= height[stack.peek()]){
            int j = stack.pop()   //记录中心柱子，即矩形的高
            int l = stack.isEmpty()? -1 : stack.peek();
            int curSize=heights[j] * (i-l-1);
            maxSize = Math.max(maxSize,curSize);
        }
        stack.push(i);
    }
    //如果栈中还有元素   那么栈中元素的右边没有比它小的数   即右边下标为heights.length
    while(!stack.isEmpty){
        int i=stack.pop();
        int l= stack.isEmpty()? -1 : stack.peek();
        int curSize = heights[i] * (heights.length-l-1);
        maxSize = Math.max(maxSize,curSize);
    }
    return maxSize;
}

3.b 进阶 最大矩形

LeetCode85.png

思路

  1. 遍历每一行， 以每一行中的几个元素为底 ， 求出每一行的最大矩形
  2. 对于每一行，都可以看成一个柱状图，如上图中的第三行 对应的柱状图 就是 [3,1,3,2,2] 这个数组生成的柱状图
  3. 每一行的柱状图 利用3.a求出最大矩形
public int maximalRectangle(char[][] matrix) {
    int m = matrix.length;
    if(m == 0) return 0;
    int n = matrix[0].length;
    int[] heights = new int[n];
    int maxArea = 0;

    for(int i = 0 ; i < m ; i++ ){
        for(int j = 0 ; j < n ; j++){
            if(matrix[i][j] == '0') heights[j] = 0;   
            else heights[j] += 1;
        }
        maxArea = Math.max(maxArea , getMaxArea(heights) );
    }
    return maxArea;
}
public int getMaxArea(int[] heights){
   //参考上题
}
  1. 给定一个非空的整数数组，返回其中出现频率前 k 高的元素

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

结合HashMap 和 堆 实现

class Solution {
    //记录数组中元素及其对应出现的次数
    Map<Integer , Integer> map = new HashMap<>();
    
    public int[] topKFrequent(int[] nums, int k) {    
        int[] heap = new int[k];
        for(int i : nums){
            map.put(i , map.getOrDefault(i,0) + 1);
        }
        Iterator it = map.keySet().iterator();
        int i = 0;
        while(it.hasNext()){
            // 先初始化一个大小为k的堆，当堆中元素个数为k时，建立小根堆
            if( i < k){
                heap[i] = (Integer)it.next();
                i++;
                if(i == k){
                    for(int j = k/2 -1 ; j >= 0 ; j--){
                        heapSort(heap,j);
                    }
                }
            }else{   //小根堆建好后 ，对于每个新遍历的元素与堆顶比较，如果比堆顶大，替换
                     //堆顶，重新维持小根堆
                int key = (Integer)it.next(); 
                if(map.get(key) > map.get(heap[0])) heap[0] = key;
                heapSort(heap , 0);
            }
            
        }
        return heap;
    }
    
    //维持小根堆
    //注意，堆中元素比较是比较它们出现的次数，即该元素在map中对应的value
    public void heapSort(int[] heap , int i){
        int temp = heap[i];
        for(int j = 2*i + 1 ; j < heap.length ; j = 2*j + 1){
            if(j+1 < heap.length && map.get(heap[j+1]) < map.get(heap[j])) j++;
            if(map.get(heap[j]) < map.get(temp)){
                heap[i] = heap[j];
                i = j;
            }else break;
        }
        heap[i] = temp;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 217,826评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,968评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,234评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,562评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,611评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,482评论 1赞 302
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,271评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,166评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,608评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,814评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,926评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,644评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,249评论 3赞 329
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,866评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,991评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,063评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,871评论 2赞 354