7.栈（七）至此栈部分结束

题目汇总：https://leetcode-cn.com/tag/stack/

剑指 Offer 30. 包含min函数的栈简单[✔]

剑指 Offer 59 - II. 队列的最大值中等[✔]

面试题 03.02. 栈的最小值简单[✔]

面试题 03.04. 化栈为队简单[✔]

面试题 08.14. 布尔运算中等（不打算做了，题解才34个）

面试题 17.21. 直方图的水量困难

剑指 Offer 30. 包含min函数的栈简单[✔]

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示： 各函数的调用总次数不超过 20000 次
注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/

思路：

维护两个栈，一个数据栈用来存所有元素，一个辅助栈用来存加入新元素之后每次的最小元素。

class MinStack {//执行用时：20 ms, 在所有 Java 提交中击败了47.21%的用户,2020/08/10
    Stack<Integer> stack_data;
    Stack<Integer> stack_min;
    /** initialize your data structure here. */
    public MinStack() {
        stack_data = new Stack<>();
        stack_min = new Stack<>();
    }
    
    public void push(int x) {
        stack_data.push(x);
        if(stack_min.isEmpty()){
            stack_min.push(x);
        }else{
            if(x > stack_min.peek()){
                stack_min.push(stack_min.peek());
            }else{
                stack_min.push(x);
            }
        }
    }
    
    public void pop() {
        stack_data.pop();
        stack_min.pop();
    }
    
    public int top() {
        return stack_data.peek();
    }
    
    public int min() {
        return stack_min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

剑指 Offer 59 - II. 队列的最大值中等[✔]

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
**输出: **[null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
**输出: **[null,-1,-1]
限制：

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5
思路：

维护两个双端队列

    ArrayDeque<Integer> valueDeque;
    ArrayDeque<Integer> maxValueDeque;//辅助双端队列
    public MaxQueue() {
        valueDeque = new ArrayDeque<>();
        maxValueDeque = new ArrayDeque<>();
    }
    
    public int max_value() {
        if(!maxValueDeque.isEmpty()) 
            return maxValueDeque.peekFirst();//peekFirst()获取双端队列的第一个元素
        return -1;
    }
    
    public void push_back(int value) {
        valueDeque.addLast(value);//addLast在双端队列后边添加元素
        while (!maxValueDeque.isEmpty() && maxValueDeque.getLast() < value) {
            maxValueDeque.pollLast();//pollLast()删除双端队列的最后一个元素
        }
        maxValueDeque.addLast(value);
    }
    
    public int pop_front() {
        if (valueDeque.isEmpty())
            return -1 ;
        else{
            int result = valueDeque.pollFirst();//pollFirst();删除双端队列的最后一个元素，返回删除元素的值
            if (result == maxValueDeque.peek())
                maxValueDeque.pollFirst();
            return result;
        }

    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

面试题 03.02. 栈的最小值简单[✔]

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

思路：

维护两个栈，第一个栈存储原来本身的元素，实现栈基本的操作；第二个栈用来存储每次在添加元素时第一个栈中的最小值。

class MinStack {//执行用时：19 ms, 在所有 Java 提交中击败了80.72%的用户,//2020/08/10
    Stack<Integer> stack_data;
    Stack<Integer> stack_min;
    /** initialize your data structure here. */
    public MinStack() {
        stack_data = new Stack<>();
        stack_min = new Stack<>();
    }
    
    public void push(int x) {
        stack_data.push(x);
        if(!stack_min.isEmpty() && stack_min.peek() < x){
            stack_min.push(stack_min.peek());
        }else{
            stack_min.push(x);
        }
    }
    
    public void pop() {
        stack_data.pop();
        stack_min.pop();
    }
    
    public int top() {
        return stack_data.peek();
    }
    
    public int getMin() {
        return stack_min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

面试题 03.04. 化栈为队简单[✔]

实现一个MyQueue类，该类用两个栈来实现一个队列。
示例：
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明：

  • 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
思路：

维护两个栈，一个用来存放插入的数，一个用来执行弹出操作。

class MyQueue {//执行用时：12 ms, 在所有 Java 提交中击败了98.62%的用户,//2020/08/10
    Stack<Integer> stack_data;//用于存放插入的数
    Stack<Integer> stack_help;//用于执行弹出操作
    /** Initialize your data structure here. */
    public MyQueue() {
        stack_data = new Stack<>();
        stack_help = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack_data.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return stack_help.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (stack_help.isEmpty()) {
            while (!stack_data.isEmpty()) {
                stack_help.push(stack_data.pop());
            }
        }
        return stack_help.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack_data.isEmpty() && stack_help.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

面试题 17.21. 直方图的水量困难

给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。


上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]，输出: 6
与42. 接雨水是一个题。

思路一：按列求的暴力法

求每一列的水，只需要关注当前列，以及左边最高的墙，右边最高的墙。
根据左右两边较矮的那个墙和当前列的墙的高度可以分为三种情况:
(1)较矮的墙的高度 > 当前列的墙的高度，这时水量是较矮的墙的高度减去当前列的墙的高度；
(2)较矮的墙的高度 < 当前列的墙的高度，这时不会有水；
(3)较矮的墙的高度 = 当前列的墙的高度，这时不会有水。
执行用时：82 ms, 在所有 Java 提交中击败了6.13%的用户
内存消耗：39.8 MB, 在所有 Java 提交中击败了5.68%的用户
时间复杂度：O(n²），空间复杂度：O(1）

class Solution {//2020/08/10
    public int trap(int[] height) {
        int sum = 0;
        for(int i = 1; i < height.length - 1; i++){
            //求出左边最高的列
            int maxleft = 0;
            for(int j = i - 1; j >= 0; j--){
                if(height[j] > maxleft){
                    maxleft = height[j];
                }
            }
            //求出右边最高的列
            int maxright = 0;
            for(int j = i + 1; j < height.length; j++){
                if(height[j] > maxright){
                    maxright = height[j];
                }
            }
            int min = Math.min(maxleft, maxright);
            //只有较小的一端大于当前列的高度才可能有水
            if(min > height[i]){
                sum += (min - height[i]);
            }
        }
    return sum;
    }
}
思路二：按列求的暴力法的优化即动态规划

对于每一列，求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里可以优化。用数组maxleft [i] 表示第 i 列左边最高的墙的高度，maxright[i]表示第 i 列右边最高的墙的高度。
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.7 MB, 在所有 Java 提交中击败了11.36%的用户
时间复杂度：O(n)，空间复杂度：O(n)

class Solution {//2020/08/10
    public int trap(int[] height) {
        int sum = 0;
        int[] maxleft = new int[height.length];
        int[] maxright = new int[height.length];
        //找出左边最高的列
        for(int i = 1; i < height.length - 1; i++){
            maxleft[i] = Math.max(maxleft[i - 1], height[i - 1]);
        }
        //找出右边最高的列
        for(int i = height.length - 2; i >= 0; i--){
            maxright[i] = Math.max(maxright[i + 1], height[i + 1]);
        }

        for(int i = 1; i < height.length - 1; i++){
            int min = Math.min(maxleft[i] ,maxright[i]);
            if(min > height[i]){
                sum += (min - height[i]);
            }
        }
    return sum;
    }
}
思路三：栈

甜姨的解题https://leetcode-cn.com/problems/trapping-rain-water/solution/dan-diao-zhan-jie-jue-jie-yu-shui-wen-ti-by-sweeti/
执行用时：4 ms, 在所有 Java 提交中击败了18.59%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了32.95%的用户
时间复杂度：O(n)，空间复杂度：O(n)

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