普通栈

栈就是一个先进后出的结构

想象一个容器，往里面一层一层放东西，最早放进去的东西被压在下面（所以放元素也叫压栈），要拿到这个最低层的东西需要先把上面的元素拿走（也叫弹栈），因此该底层元素最后弹出，即先进后出

Stack用法

// 创建一个堆栈对象
Stack<Integer> stack = new Stack<>();
// 入栈操作
stack.push(5);
stack.push(3);
stack.push(8);
// 出栈操作
int topElement = stack.pop();
// 查看栈顶元素
int peekElement = stack.peek();
// 判断堆栈是否为空
boolean isEmpty = stack.isEmpty();
// 获取堆栈中的元素个数
int size = stack.size();

Q 最长有效括号

32. 最长有效括号 - 力扣（LeetCode）

左括号压栈，右括号弹栈匹配并更新答案，整个过程记录的最大值就是答案

public int longestValidParentheses(String s) {int res = 0;// Deque的LinkedList非同步，不如stack安全，但是快，开销少Deque<Integer> stack = new LinkedList<>();stack.push(-1);  // 初始化栈，确保第一个如果是 ) 的话，弹出不会有该报错：栈中无元素for (int i = 0; i < s.length(); i++) {// 1、左括号压栈 if (s.charAt(i) == '(') {stack.push(i); // 压入的是此时左括号对应的下标索引} // 2、右括号弹栈else {stack.pop();if (stack.isEmpty())   stack.push(i);  // 弹栈后栈空，说明没有左括号和它匹配// 因此压入当前右括号索引，此时 i - stack.peek() = 0，即没有有效括号长度else   res = Math.max(res, i - stack.peek());// 栈最顶的元素的索引与当前索引之差，就是当前子部分的有效括号长度，可能更新答案}}return res;
}

单调栈

在栈结构的基础上，栈中元素满足单调性（单调递增或递减）

Q 接雨水

42. 接雨水 - 力扣（LeetCode）

• 注意：这里的栈，存的是高度height[]数组的索引，按从小到大遍历顺序来决定入栈出栈，因此很明显满足单调性（单调递增）
• 中间部分可能有点乱，我画个图方便大家理解下
  

public int trap(int[] height) {int ans = 0;Deque<Integer> stack = new LinkedList<Integer>();int n = height.length;for (int i = 0; i < n; ++i) {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int top = stack.pop();if (stack.isEmpty()) {break;  // 这种情况表示栈中只有一个元素，新增的高度还大于这个元素，没凹槽肯定接不了雨水，直接break}// 这种情况表示栈中不止一个元素，而是有一个单调递减的阶梯，目前left = peek的阶梯是左边最矮的墙// top 则是最凹槽的位置， height[i]则表示凹槽右边当前遍历到的墙高int left = stack.peek();int currWidth = i - left - 1;int currHeight = Math.min(height[left], height[i]) - height[top];ans += currWidth * currHeight;// 每算出一个答案的过程，单调栈都会 弹出/减掉最右侧/栈顶 那个最矮的墙壁，因为已经用来计算好对应的雨水了}stack.push(i); // 情况1：栈中一个元素都没有，肯定没办法接雨水，需要把当前的墙高加进去（墙高可以为0）// 情况2：当前的高度值<左侧的高度值，那么入栈，等后面和弹栈匹配来计算雨水数量}return ans;
}