题目汇总：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的总操作数 <= 100001 <= 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;
}
}
网友评论