算法02-栈和队列的实现与特性

《算法练习-文章汇总》

栈:先进后出

stack:添加和删除为O(1),查询为O(n)

队列:先进先出

queue:添加和删除为O(1),查询为O(n)

示例代码-Stack

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack);
System.out.println(stack.search(4));

stack.pop();
stack.pop();
Integer topElement = stack.peek();
System.out.println(topElement);
System.out.println("3的位置"+stack.search(3));

示例代码-Queue

Queue<String> queue = new LinkedList<String>();
queue.offer("one");
queue.offer("two");
queue.offer("three");
queue.offer("four");
System.out.println(queue);

String polledElement = queue.poll();
System.out.println(polledElement);
System.out.println(queue);

String peekedElement = queue.peek();
System.out.println(peekedElememt);
System.out.println(queue);

while(queue.size()>0){
   System.out.println(queue.poll());
}

示例代码-Deque

Deque<String> deque = new LinkedList<String>();
deque.push("a");
deque.push("b");
deque.push("c");
System.out.println(deque);

String str = deque.peek();
System.out.println(str);
System.out.println(deque);

while(deque.size()>0){
   System.out.println(deque.pop());
}

System.out.println(deque);

Priority Queue

  • 1.插入操作:O(1);
  • 2.取出操作:O(logN)-按照元素的优先级取出
  • 3.底层具体实现的数据结构较为多样和复杂:heap

Java源码分析:
Stack:http://develop.classpath.org/doc/java/util/Stack-source.html
Queue:http://fuseyism.com/classpath/doc/java/util/Queue-source.html

作业:分析Queue和Priority Queue的源码

柱状图中最大矩形

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

1.暴力法

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int maxArea = 0;
        for(int left = 0;left < length;left++){
            int minHeight = Integer.MAX_VALUE;
            for(int right = left;right < length;right++){ 
                minHeight = Math.min(minHeight,heights[right]);
                maxArea = Math.max(maxArea,minHeight * (right - left + 1));
            }
        }
        return maxArea;
    }
}

2.栈

维护一个栈,一开始,把-1放进栈的顶部来表示开始。初始化时,按照从左到右的顺序,不断将柱子的需要放进栈中,知道遇到相邻柱子呈下降关系,也就是a[i-1]>a[i]。现在我们开始将栈中的序号弹出,知道遇到stack[j]满足a[stack[j]]<= a[i]。每次我们弹出下标时,我们用弹出元素作为高形成的最大面积矩形的宽是当前元素与stack[top - 1]之间的那些柱子。也就是当我们淡出stack[top]时,记当前元素在原数组中的下标为i,当前弹出元素为高的最大矩形面积为:
(i - stack[top - 1] - 1) * a[stack[top]]

    public int largestRectangleArea1(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxarea = 0;
        for (int i=0;i<heights.length;++i){
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
            maxarea = Math.max(maxarea,heights[stack.pop()] * (i - stack.peek() -1));
            stack.push(i);
        }
        while (stack.peek() != -1){
            maxarea = Math.max(maxarea,heights[stack.pop()] * (heights.length-1-stack.peek()));
        }
        return maxarea;
    }

3.单调栈

以上暴力写法 Java 可以通过,但我们不妨想一下这里的双重循环是否可以优化?

我们每遍历到当前柱体 i 时:

上述写法中,我们需要再嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体,这个过程是 O(N)O(N) 的;
那么我们可以 O(1)O(1) 的获取柱体 i 左边第一个比它小的柱体吗?答案就是单调增栈,因为对于栈中的柱体来说,栈中下一个柱体就是左边第一个高度小于自身的柱体。
因此做法就很简单了,我们遍历每个柱体,若当前的柱体高度大于等于栈顶柱体的高度,就直接将当前柱体入栈,否则若当前的柱体高度小于栈顶柱体的高度,说明当前栈顶柱体找到了右边的第一个小于自身的柱体,那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length); 
        
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 对栈中柱体来说,栈中的下一个柱体就是其「左边第一个小于自身的柱体」;
            // 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积🌶️ ~
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int h = tmp[stack.pop()];
                area = Math.max(area, (i - stack.peek() - 1) * h);   
            }
            stack.push(i);
        }

        return area;
    }
}

滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/

1.暴力法

最简单直接的方法是遍历每个滑动窗口,找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口,每个有 k 个元素,于是算法的时间复杂度为 {O}(N k)O(Nk),表现较差。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        
        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++) 
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }
}
复杂度分析

时间复杂度:{O}(N k)O(Nk)。其中 N 为数组中元素个数。

空间复杂度:{O}(N - k + 1)O(N−k+1),用于输出数组。

2.双端队列

class Queue {
    void push(int n);
    // 或 enqueue,在队尾加入元素 n
    void pop();
    // 或 dequeue,删除队头元素
}
class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n,删除它
    void pop(int n);
}
class deque {
    // 在队头插入元素 n
    void push_front(int n);
    // 在队尾插入元素 n
    void push_back(int n);
    // 在队头删除元素
    void pop_front();
    // 在队尾删除元素
    void pop_back();
    // 返回队头元素
    int front();
    // 返回队尾元素
    int back();
}

public int[] maxSlidingWindow(int[] a, int k) {     
        if (a == null || k <= 0) {
            return new int[0];
        }
        int n = a.length;
        int[] r = new int[n-k+1];
        int ri = 0;
        // store index
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            // remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
                q.pollLast();
            }
            // q contains index... r contains content
            q.offer(i);
            if (i >= k - 1) {
                r[ri++] = a[q.peek()];
            }
        }
        return r;
    }

预习题目

有效的括号
https://leetcode-cn.com/problems/valid-parentheses/

    //有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (Character c:s.toCharArray()){
            if (c == '(') stack.push(')');
            else if(c == '[') stack.push(']');
            else if(c == '{') stack.push('}');
            else if(stack.isEmpty()|| stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }

最小栈
https://leetcode-cn.com/problems/min-stack/

class MinStack {

    Stack<Integer>  stack;
    Stack<Integer>  minStack;
    public MinStack(){
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int n){
        stack.push(n);
        if(minStack.isEmpty() || n <= minStack.peek())
        minStack.push(n);
    }
    public void pop(){
            if(stack.pop().equals(minStack.peek()))
            minStack.pop();
    }
    public int top(){
        return stack.peek();
    }
    
    public int getMin(){
        return minStack.peek();
    }
}

课后作业

设计循环双端队列
https://leetcode-cn.com/problems/design-circular-deque/

设计实现双端队列。
你的实现需要支持以下操作:

MyCircularDeque(k):构造函数,双端队列的大小为k。
insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast():将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront():从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast():从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront():从双端队列头部获得一个元素。如果双端队列为空,返回 -1。
getRear():获得双端队列的最后一个元素。 如果双端队列为空,返回 -1。
isEmpty():检查双端队列是否为空。
isFull():检查双端队列是否满了。
示例:

MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);                    // 返回 true
circularDeque.insertLast(2);                    // 返回 true
circularDeque.insertFront(3);                   // 返回 true
circularDeque.insertFront(4);                   // 已经满了,返回 false
circularDeque.getRear();                // 返回 2
circularDeque.isFull();                     // 返回 true
circularDeque.deleteLast();                 // 返回 true
circularDeque.insertFront(4);                   // 返回 true
circularDeque.getFront();               // 返回 4

提示:
所有值的范围为 [1, 1000]
操作次数的范围为 [1, 1000]
请不要使用内置的双端队列库

public class MyCircularDeque {
    // 1、不用设计成动态数组,使用静态数组即可
    // 2、设计 head 和 tail 指针变量
    // 3、head == tail 成立的时候表示队列为空
    // 4、tail + 1 == head
    private int capacity;
    private int[] arr;
    private int front;
    private int rear;

    public MyCircularDeque(int k){
        capacity = k + 1;
        arr = new int[capacity];
        // 头部指向第 1 个存放元素的位置
        // 插入时,先减,再赋值
        // 删除时,索引 +1(注意取模)
        front = 0;
        // 尾部指向下一个插入元素的位置
        // 插入时,先赋值,再加
        // 删除时,索引 -1(注意取模)
        rear = 0;
    }

    public boolean insertFront(int value){
        if (isFull()){
            return false;
        }
        front = (front -1 + capacity)%capacity;
        arr[front] = value;
        return true;
    }

    public boolean insertLast(int value){
        if(isFull()){
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1)% capacity;
        return true;
    }

    public boolean deleteFront(){
        if (isEmpty())
        return false;
        // front 被设计在数组的开头,所以是 +1
        front = (front + 1) % capacity;
        return true;
    }

    public boolean deleteLast(){
        if (isEmpty()) return  false;
        // rear 被设计在数组的末尾,所以是 -1
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    public int getFront(){
        if (isEmpty()) return  -1;
        return arr[front];
    }

    public int getRear(){
        if (isEmpty()) return -1;
        // 当 rear 为 0 时防止数组越界
        return arr[(rear -1 + capacity) % capacity];
    }

    public boolean isEmpty(){
        return front == rear;
    }

    public boolean isFull(){
        // 注意:这个设计是非常经典的做法
         return (rear+1) %capacity == front;
    }
}

接雨水
https://leetcode-cn.com/problems/trapping-rain-water/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

接雨水.png

方法一:暴力法

直观想法

直接按问题描述进行。对于数组中的每个元素,我们找出下雨后水能达到的最高位置,等于两边最大高度的较小值减去当前高度的值。
算法

初始化 ans=0ans=0
从左向右扫描数组:

初始化 \text{max_left}=0max_left=0 和 \text{max_right}=0max_right=0

从当前元素向左扫描并更新:
\text{max_left}=\max(\text{max_left},\text{height}[j])max_left=max(max_left,height[j])

从当前元素向右扫描并更新:
\text{max_right}=\max(\text{max_right},\text{height}[j])max_right=max(max_right,height[j])

将\min(\text{max_left},\text{max_right}) - \text{height}[i]min(max_left,max_right)−height[i] 累加到 \text{ans}ans

    public int requireRain(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i ; j >= 0; j--) {
                max_left = Math.max(max_left, nums[j]);
            }
            for (int k = i; k < nums.length; k++) {
                max_right = Math.max(nums[k], max_right);
            }
            ans += (Math.min(max_left, max_right) - nums[i]);
        }
        return ans;
    }

方法二:栈

直观想法

我们可以不用像方法 2 那样存储最大高度,而是用栈来跟踪可能储水的最长的条形块。使用栈就可以在一次遍历内完成计算。

我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到 \text{ans}ans 。

算法

使用栈来存储条形块的索引下标。
遍历数组:
当栈非空且 \text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
意味着栈中元素可以被弹出。弹出栈顶元素 \text{top}top。
计算当前元素和栈顶元素的距离,准备进行填充操作
\text{distance} = \text{current} - \text{st.top}() - 1distance=current−st.top()−1

找出界定高度

\text{bounded_height} = \min(\text{height[current]}, \text{height[st.top()]}) - \text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times \text{bounded_height}ans+=distance×bounded_height
将当前索引下标入栈
将 \text{current}current 移动到下个位置

    public int requireRain0(int[] nums) {
        int ans = 0;
        int currentIndex = 0;
        Stack<Integer> stack = new Stack<>();
        while (currentIndex < nums.length){
            while (!stack.isEmpty() && nums[currentIndex] > nums[stack.peek()]){
               int top = stack.peek();
               stack.pop();
               if (stack.isEmpty())
                   break;
               int distance = currentIndex - stack.peek() - 1;
               int boundHight = Math.min(nums[currentIndex],nums[stack.peek()])-nums[top];
               ans += distance*boundHight;
            }
            stack.push(currentIndex++);
        }
        return ans;
    }

方法三:双指针

直观想法
想办法一次完成遍历。
我们注意到,只要 \text{right_max}[i]>\text{left_max}[i]right_max[i]>left_max[i] (元素 0 到元素 6),积水高度将由 left_max 决定,类似地 \text{left_max}[i]>\text{right_max}[i]left_max[i]>right_max[i](元素 8 到元素 11)。
所以我们可以认为如果一端有更高的条形块(例如右端),积水的高度依赖于当前方向的高度(从左到右)。当我们发现另一侧(右侧)的条形块高度不是最高的,我们则开始从相反的方向遍历(从右到左)。
我们必须在遍历时维护 \text{left_max}left_max 和 \text{right_max}right_max ,但是我们现在可以使用两个指针交替进行,实现 1 次遍历即可完成。

算法
初始化 \text{left}left 指针为 0 并且 \text{right}right 指针为 size-1
While \text{left}< \text{right}left<right, do:
If \text{height[left]}height[left] < \text{height[right]}height[right]
If \text{height[left]} \geq \text{left_max}height[left]≥left_max, 更新 \text{left_max}left_max
Else 累加 \text{left_max}-\text{height[left]}left_max−height[left] 到 \text{ans}ans
\text{left}left = \text{left}left + 1.
Else
If \text{height[right]} \geq \text{right_max}height[right]≥right_max, 更新 \text{right_max}right_max
Else 累加 \text{right_max}-\text{height[right]}right_max−height[right] 到 \text{ans}ans
\text{right}right = \text{right}right - 1.

C++

int Solution::trap(std::vector<int>& height)
{
    int left = 0,right = height.size()-1;
    int left_max = 0,right_max = 0;
    int ans = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            height[left] >= left_max ? left_max = height[left]: ans += (left_max-height[left]);
            left++;
        }else{
            height[right] >= right_max ? right_max = height[right] : ans += (right_max - height[right]);
            right--;
        }
    }
    return ans;
}

Java

    public int trap(int[] height){
        int left = 0,right = height.length - 1;
        int left_max = 0,right_max = 0;
        int ans = 0;
        while (left < right){
            if (height[left] < height[right]){
                if(height[left] >= left_max){
                    left_max = height[left];
                } else {
                    ans += (left_max - height[left]);
                }
                left++;
            }else {
                if (height[right] >= right_max){
                    right_max = height[right];
                }else{
                    ans += (right_max - height[right]);
                }
                right--;
            }
        }
        return ans;
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,968评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,601评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,220评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,416评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,425评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,144评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,432评论 3 401
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,088评论 0 261
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,586评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,783评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,343评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2 345

推荐阅读更多精彩内容