不要纠结，干就完事了，熟练度很重要！！！多练习，多总结！！！

LeetCode 20. 有效的括号

解题思路

遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配，最后记得检查栈是否清空了，这才算匹配完成。

代码实现

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char c:s.toCharArray()){if(c == '(' || c == '{' || c == '['){stack.push(c);}else if(!stack.isEmpty() && leftOf(c) == stack.peek()){stack.pop();}else {return false;}}return stack.isEmpty();}public char leftOf(char c){if(c == ')'){return '(';}else if(c == ']'){return '[';}else if(c == '}'){return '{';}return ' ';}
}

LeetCode 921. 使括号有效的最少添加

解题思路

核心思路是以左括号为基准，通过维护对右括号的需求数need，来计算最小的插入次数。需要注意两个地方：

1. 当need == -1的时候意味着什么？

因为只有遇到右括号)的时候才会need–，need == -1意味着右括号太多了，所以需要插入左括号。
比如说s = “))“这种情况，需要插入 2 个左括号，使得s变成”()()”，才是一个合法括号串。

2. 算法为什么返回res + need？

因为res记录的左括号的插入次数，need记录了右括号的需求，当 for 循环结束后，若need不为 0，那么就意味着右括号还不够，需要插入。
比如说s = “))(“这种情况，插入 2 个左括号之后，还要再插入 1 个右括号，使得s变成”()()()”，才是一个合法括号串。

代码实现

class Solution {public int minAddToMakeValid(String s) {int res = 0, need = 0;for(char c: s.toCharArray()){if(c == '('){need++;}else if(c == ')'){need--;if(need == -1){res++;need = 0;}}}return res+need;}
}

LeetCode 1541. 平衡括号字符串的最少插入次数

解题思路

1. 当need == -1时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号。

if (s[i] == ')') {need--;// 说明右括号太多了if (need == -1) {// 需要插入一个左括号res++;// 同时，对右括号的需求变为 1need = 1;}
}

2. 当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号。因为一个左括号需要两个右括号嘛，右括号的需求必须是偶数。（记住res和need代表含义不同，一加一减不可抵消，在need==-1时还有额外判断逻辑）

if (s[i] == '(') {need += 2;if (need % 2 == 1) {// 插入一个右括号res++;// 对右括号的需求减一need--;}
}

代码实现

class Solution {public int minInsertions(String s) {int res = 0, need = 0;for(char c :s.toCharArray()){if(c == '('){need+=2;if (need % 2 == 1) {res++;need--;}}else if(c == ')'){need--;if(need == -1){res++;need = 1;}}}return res+need;}
}

单调栈

输入一个数组nums = [2,1,2,4,3]，你返回数组[4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

int[] nextGreaterElement(int[] nums) {int n = nums.length;// 存放答案的数组int[] res = new int[n];Stack<Integer> s = new Stack<>(); // 倒着往栈里放for (int i = n - 1; i >= 0; i--) {// 判定个子高矮while (!s.isEmpty() && s.peek() <= nums[i]) {// 矮个起开，反正也被挡着了。。。s.pop();}// nums[i] 身后的更大元素res[i] = s.isEmpty() ? -1 : s.peek();s.push(nums[i]);}return res;
}

LeetCode 496. 下一个更大元素 I

解题思路

题目说nums1是nums2的子集，那么我们先把nums2中每个元素的下一个更大元素算出来存到一个映射里，然后再让nums1中的元素去查表即可。

代码实现

class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] greater = nextGreater(nums2);Map<Integer, Integer> map = new HashMap<>();for(int i = 0;i < greater.length;i++){map.put(nums2[i], greater[i]);}int[] res = new int[nums1.length];for(int i = 0;i < nums1.length;i++){res[i] = map.get(nums1[i]);}return res;}public int[] nextGreater(int[] nums){int n = nums.length;int[] res = new int[n];Stack<Integer> stack = new Stack<>();for(int i = n-1;i >= 0;i--){while(!stack.isEmpty() && stack.peek() < nums[i]){stack.pop();}res[i] = stack.isEmpty()? -1 : stack.peek();stack.push(nums[i]);}return res;}
}

LeetCode 739. 每日温度

解题思路

该题思路同《LeetCode 496. 下一个更大元素 I》不同点在于要求的是当前值与之后最大值的间隔。

代码实现

class Solution {public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;int[] res = new int[n];Stack<Integer> stack = new Stack<>();for(int i = n-1;i >=0 ;i--){while(!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]){stack.pop();}res[i] = stack.isEmpty()? 0 : (stack.peek()-i);stack.push(i);}return res;}
}

LeetCode 503. 下一个更大元素 II

解题思路

题目要求环形数组，对于这种需求，常用套路就是将数组长度翻倍：

代码实现

class Solution {public int[] nextGreaterElements(int[] nums) {int n = nums.length;int[] res = new int[n];Stack<Integer> stack = new Stack<>();for(int i = 2*n-1;i >= 0;i--){while(!stack.isEmpty() && stack.peek() <= nums[i%n]){stack.pop();}res[i%n] = stack.isEmpty() ? -1: stack.peek();stack.push(nums[i%n]);}return res;}
}

单调队列

如果每个元素被加入时都这样操作，最终单调队列中的元素大小就会保持一个单调递减的顺序。

/* 单调队列的实现 */
class MonotonicQueue {LinkedList<Integer> maxq = new LinkedList<>();public void push(int n) {// 将小于 n 的元素全部删除while (!maxq.isEmpty() && maxq.getLast() < n) {maxq.pollLast();}// 然后将 n 加入尾部maxq.addLast(n);}public int max() {return maxq.getFirst();}public void pop(int n) {if (n == maxq.getFirst()) {maxq.pollFirst();}}
}

为啥要发明「单调队列」这种结构呢，主要是为了解决下面这个场景：

给你一个数组window，已知其最值为A，如果给window中添加一个数B，那么比较一下A和B就可以立即算出新的最值；但如果要从window数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是A，就需要遍历window中的所有元素重新寻找新的最值。

如果单纯地维护最值的话，优先级队列很专业，队头元素就是最值。但优先级队列无法满足标准队列结构「先进先出」的时间顺序，因为优先级队列底层利用二叉堆对元素进行动态排序，元素的出队顺序是元素的大小顺序，和入队的先后顺序完全没有关系。

与双指针的滑动窗口不同 ，每当窗口扩大（right++）和窗口缩小（left++）时，你单凭移出和移入窗口的元素即可决定是否更新答案。

但就本文开头说的那个判断一个窗口中最值的例子，你就无法单凭移出窗口的那个元素更新窗口的最值，除非重新遍历所有元素，但这样的话时间复杂度就上来了。

LeetCode 239. 滑动窗口最大值

解题思路

代码实现

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {List<Integer> list = new ArrayList<>();MaxQueue queue = new MaxQueue();for(int i = 0;i < nums.length;i++){if(i < k-1){queue.push(nums[i]);}else{queue.push(nums[i]);list.add(queue.max());queue.pop(nums[i-k+1]);}}int[] res = new int[list.size()];for(int i = 0; i < list.size();i++){res[i] = list.get(i);}return res;}
}class MaxQueue{LinkedList<Integer> queue = new LinkedList<>();public void push(int n){while(!queue.isEmpty() && queue.getLast() < n){queue.pollLast();}queue.addLast(n);}public int max(){return queue.getFirst();}public void pop(int n){if(!queue.isEmpty() && queue.getFirst() == n){queue.pollFirst();}}
}

数组去重

LeetCode 316. 去除重复字母

解题思路

要求一、要去重。

要求二、去重字符串中的字符顺序不能打乱s中字符出现的相对顺序。

要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。

在stk.peek() > c时才会 pop 元素，其实这时候应该分两种情况：
情况一、如果stk.peek()这个字符之后还会出现，那么可以把它 pop 出去，反正后面还有嘛，后面再 push 到栈里，刚好符合字典序的要求。
情况二、如果stk.peek()这个字符之后不会出现了，前面也说了栈中不会存在重复的元素，那么就不能把它 pop 出去，否则你就永远失去了这个字符。

总结

• 要求一、通过inStack这个布尔数组做到栈stk中不存在重复元素。
• 要求二、我们顺序遍历字符串s，通过「栈」这种顺序结构的 push/pop 操作记录结果字符串，保证了字符出现的顺序和s中出现的顺序一致。
  这里也可以想到为什么要用「栈」这种数据结构，因为先进后出的结构允许我们立即操作刚插入的字符，如果用「队列」的话肯定是做不到的。
• 要求三、我们用类似单调栈的思路，配合计数器count不断 pop 掉不符合最小字典序的字符，保证了最终得到的结果字典序最小。
  当然，由于栈的结构特点，我们最后需要把栈中元素取出后再反转一次才是最终结果。

代码实现

class Solution {public String removeDuplicateLetters(String s) {Stack<Character> stack = new Stack<>();boolean[] flag = new boolean[256];int[] count = new int[256];for(char c : s.toCharArray()){count[c]++;}for(char c : s.toCharArray()){count[c]--;if(flag[c]){continue;}while(!stack.isEmpty() && stack.peek() > c){if(count[stack.peek()] == 0){break;}flag[stack.pop()]=false;}stack.push(c);flag[c]=true;}StringBuilder sb = new StringBuilder();while(!stack.isEmpty()){sb.append(stack.pop());}return sb.reverse().toString();}
}

总结

本题来源于Leetcode中 归属于队列、栈类型题目。
同许多在算法道路上不断前行的人一样，不断练习，修炼自己！
如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！

觉得本博客有用的客官，可以给个点赞+收藏哦！ 嘿嘿

喜欢本系列博客的可以关注下，以后除了会继续更新面试手撕代码文章外，还会出其他系列的文章！