1.队列

1.1 【中等】设计循环双端队列（641）

image.png

  1. /**
  2.  * 可使用Deque，或者直接阅读源码
  3.  */
  4. class MyCircularDeque {
  5.     private Deque<Integer> deque;
  6.     private Integer count;
  8.     public MyCircularDeque(int k) {
  9.         deque = new ArrayDeque<>();
  10.         this.count = k;
  11.     }
  13.     public boolean insertFront(int value) {
  14.         if (isFull()) {
  15.             return false;
  16.         }
  17.         deque.addFirst(value);
  18.         return true;
  19.     }
  21.     public boolean insertLast(int value) {
  22.         if (isFull()) {
  23.             return false;
  24.         }
  25.         deque.addLast(value);
  26.         return true;
  27.     }
  29.     public boolean deleteFront() {
  30.         if (isEmpty()) {
  31.             return false;
  32.         }
  33.         deque.removeFirst();
  34.         return true;
  35.     }
  37.     public boolean deleteLast() {
  38.         if (isEmpty()) {
  39.             return false;
  40.         }
  41.         deque.removeLast();
  42.         return true;
  43.     }
  45.     public int getFront() {
  46.         if (isEmpty()) {
  47.             return -1;
  48.         }
  49.         return deque.getFirst();
  50.     }
  52.     public int getRear() {
  53.         if (isEmpty()) {
  54.             return -1;
  55.         }
  56.         return deque.getLast();
  57.     }
  59.     public boolean isEmpty() {
  60.         return deque == null || deque.size() == 0;
  61.     }
  63.     public boolean isFull() {
  64.         return deque.size() == count;
  65.     }
  66. }

1.2 【困难】滑动窗口最大值（239）

image.png

  1. /**
  2.  * 使用优先级队列最大堆，数组0:值，数组1:下标
  3.  */
  4. public int[] maxSlidingWindow(int[] nums, int k) {
  5.     int n = nums.length;
  6.     PriorityQueue<int[]> pq = new PriorityQueue<>(
  7.             (pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[
  8.     for (int i = 0; i < k; ++i) {
  9.         pq.offer(new int[]{nums[i], i});
  10.     }
  11.     int[] ans = new int[n - k + 1];
  12.     ans[0] = pq.peek()[0];
  13.     for (int i = k; i < n; ++i) {
  14.         pq.offer(new int[]{nums[i], i});
  15.         while (pq.peek()[1] <= i - k) {
  16.             pq.poll();
  17.         }
  18.         ans[i - k + 1] = pq.peek()[0];
  19.     }
  20.     return ans;
  21. }

1.3 【中等】层次遍历二叉树（102）

image.png

  1. /**
  2.  * 使用队列
  3.  */
  4. public List<List<Integer>> levelOrder(TreeNode root) {
  5.     List<List<Integer>> ret = new ArrayList<>();
  6.     if (root == null) {
  7.         return ret;
  8.     }
  9.     Queue<TreeNode> queue = new LinkedList<>();
  10.     queue.offer(root);
  11.     while (!queue.isEmpty()) {
  12.         List<Integer> level = new ArrayList<>();
  13.         int currentLevelSize = queue.size();
  14.         for (int i = 1; i <= currentLevelSize; ++i) {
  15.             TreeNode node = queue.poll();
  16.             level.add(node.val);
  17.             if (node.left != null) {
  18.                 queue.offer(node.left);
  19.             }
  20.             if (node.right != null) {
  21.                 queue.offer(node.right);
  22.             }
  23.         }
  24.         ret.add(level);
  25.     }
  26.     return ret;
  27. }

2.栈

2.1 【简单】最小栈（155）

image.png

  1. /**
  2.  * 使用两个栈进行配合
  3.  */
  4. class MinStack {
  6.     Deque<Integer> xStack;
  7.     Deque<Integer> minStack;
  9.     public MinStack() {
  10.         xStack = new LinkedList<>();
  11.         minStack = new LinkedList<>();
  12.         minStack.push(Integer.MAX_VALUE);
  13.     }
  15.     public void push(int x) {
  16.         xStack.push(x);
  17.         minStack.push(Math.min(minStack.peek(), x));
  18.     }
  20.     public void pop() {
  21.         xStack.pop();
  22.         minStack.pop();
  23.     }
  25.     public int top() {
  26.         return xStack.peek();
  27.     }
  29.     public int getMin() {
  30.         return minStack.peek();
  31.     }
  32. }

2.2 【简单】有效括号（20）

image.png

  1. /**
  2.  * 使用一个栈就可以了，左半边压栈，右半边出栈，如果为空或者不为对应符号，就返回错误
  3.  */
  4. public boolean isValid(String s) {
  5.     int n = s.length();
  6.     if (n % 2 == 1) {
  7.         return false;
  8.     }
  9.     Map<Character, Character> pairs = new HashMap<Character, Character>() {{
  10.         put(')', '(');
  11.         put(']', '[');
  12.         put('}', '{');
  13.     }};
  14.     Deque<Character> stack = new LinkedList<>();
  15.     for (int i = 0; i < n; i++) {
  16.         char ch = s.charAt(i);
  17.         if (pairs.containsKey(ch)) {
  18.             if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) {
  19.                 return false;
  20.             }
  21.             stack.pop();
  22.         } else {
  23.             stack.push(ch);
  24.         }
  25.     }
  26.     return stack.isEmpty();
  27. }

2.3 【困难】接雨水（42）

image.png

  1. /**
  2.  * 循环使用单调栈
  3.  */
  4. public int trap(int[] height) {
  5.     Deque<Integer> stack = new LinkedList<>();
  6.     int result = 0;
  7.     for (int i = 0; i < height.length; ++i) {
  8.         while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
  9.             int top = stack.pop();
  10.             if (stack.isEmpty()) {
  11.                 break;
  12.             }
  13.             int left = stack.peek();
  14.             int widthTemp = i - left - 1;
  15.             int heightTemp = Math.min(height[left], height[i]) - height[top];
  16.             result += widthTemp * heightTemp;
  17.         }
  18.         stack.push(i);
  19.     }
  20.     return result;
  21. }

2.4 【困难】柱状图中最大的矩形（84）

image.png

  1. /**
  2.  * 正反单调栈
  3.  */
  4. public int largestRectangleArea(int[] heights) {
  5.     int n = heights.length;
  6.     int[] left = new int[n];
  7.     int[] right = new int[n];
  8.     Deque<Integer> monoStack = new ArrayDeque<>();
  9.     for (int i = 0; i < n; ++i) {
  10.         while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
  11.             monoStack.pop();
  12.         }
  13.         left[i] = (monoStack.isEmpty() ? -1 : monoStack.peek());
  14.         monoStack.push(i);
  15.     }
  16.     monoStack.clear();
  17.     for (int i = n - 1; i >= 0; --i) {
  18.         while (!monoStack.isEmpty() && heights[monoStack.peek()] >= heights[i]) {
  19.             monoStack.pop();
  20.         }
  21.         right[i] = (monoStack.isEmpty() ? n : monoStack.peek());
  22.         monoStack.push(i);
  23.     }
  24.     int ans = 0;
  25.     for (int i = 0; i < n; ++i) {
  26.         ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
  27.     }
  28.     return ans;
  29. }

2.5 【中等】每日温度（739）

image.png

  1. /**
  2.  * 使用单调栈即可，后往前遍历
  3.  */
  4. public int[] dailyTemperatures(int[] temperatures) {
  5.     int n = temperatures.length;
  6.     int[] res = new int[n];
  7.     int[] index = new int[n];
  8.     Deque<Integer> dq = new LinkedList<>();
  9.     for (int i = n-1; i >=0; i--) {
  10.         while (!dq.isEmpty() && temperatures[i] >= temperatures[dq.peek()]) {
  11.             dq.pop();
  12.         }
  13.         index[i] = dq.isEmpty() ? i : dq.peek();
  14.         dq.push(i);
  15.     }
  16.     for (int i = 0; i < n; i++) {
  17.         res[i] = index[i] - i;
  18.     }
  19.     return res;
  20. }

2.6 【简单】下一个更大元素 I（496）

image.png

  1. /**
  2.  * 第 1 个子问题：如何更高效地计算nums2中每个元素右边的第一个更大的值；
  3.  * 第 2 个子问题：如何存储第 1 个子问题的结果。
  4.  * 使用单调栈即可，后往前遍历
  5.  */
  6. public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  7.     Map<Integer, Integer> map = new HashMap<>();
  8.     Deque<Integer> stack = new ArrayDeque<>();
  9.     for (int i = nums2.length - 1; i >= 0; --i) {
  10.         int num = nums2[i];
  11.         while (!stack.isEmpty() && num >= stack.peek()) {
  12.             stack.pop();
  13.         }
  14.         map.put(num, stack.isEmpty() ? -1 : stack.peek());
  15.         stack.push(num);
  16.     }
  17.     int[] res = new int[nums1.length];
  18.     for (int i = 0; i < nums1.length; ++i) {
  19.         res[i] = map.get(nums1[i]);
  20.     }
  21.     return res;
  22. }

2.7 【中等】 去除重复字母（316）

image.png

  1. /**
  2.  * 有点难，死记就好了，需要用到单调栈
  3.  */
  4. public static String removeDuplicateLetters(String s) {
  5.     boolean[] vis = new boolean[26];
  6.     int[] num = new int[26];
  7.     // 统计每个字符个数
  8.     for (int i = 0; i < s.length(); i++) {
  9.         num[s.charAt(i) - 'a']++;
  10.     }
  11.     StringBuffer sb = new StringBuffer();
  12.     for (int i = 0; i < s.length(); i++) {
  13.         char ch = s.charAt(i);
  14.         if (!vis[ch - 'a']) {
  15.             // 单调栈
  16.             while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
  17.                 if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
  18.                     vis[sb.charAt(sb.length() - 1) - 'a'] = false;
  19.                     sb.deleteCharAt(sb.length() - 1);
  20.                 } else {
  21.                     break;
  22.                 }
  23.             }
  24.             vis[ch - 'a'] = true;
  25.             sb.append(ch);
  26.         }
  27.         // 个数减一
  28.         num[ch - 'a'] -= 1;
  29.     }
  30.     return sb.toString();
  31. }

2.8 【中等】 股票价格跨度（901）

image.png

  1. /**
  2.  * 单调栈
  3.  */
  4. public class StockSpanner {
  5.     Stack<Integer> prices, weights;
  7.     public StockSpanner() {
  8.         prices = new Stack();
  9.         weights = new Stack();
  10.     }
  12.     public int next(int price) {
  13.         int w = 1;
  14.         // 向前出栈，找到比这天更大的数据
  15.         while (!prices.isEmpty() && prices.peek() <= price) {
  16.             prices.pop();
  17.             w += weights.pop();
  18.         }
  20.         prices.push(price);
  21.         weights.push(w);
  22.         return w;
  23.     }
  24. }

2.9 【中等】 移掉K位数字（402）

image.png

  1. /**
  2.  * 单调栈
  3.  */
  4. public String removeKdigits(String num, int k) {
  5.     Deque<Character> deque = new LinkedList<>();
  6.     int length = num.length();
  7.     for (int i = 0; i < length; ++i) {
  8.         char digit = num.charAt(i);
  9.         // 单调栈 如果前一个元素比后一个元素大，直接删就可以了，肯定会比不删小
  10.         while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
  11.             deque.pollLast();
  12.             k--;
  13.         }
  14.         deque.offerLast(digit);
  15.     }
  16.     // 如果没有删完，继续删
  17.     for (int i = 0; i < k; ++i) {
  18.         deque.pollLast();
  19.     }
  20.     StringBuilder ret = new StringBuilder();
  21.     boolean leadingZero = true;
  22.     // 删除前面的0
  23.     while (!deque.isEmpty()) {
  24.         char digit = deque.pollFirst();
  25.         if (leadingZero && digit == '0') {
  26.             continue;
  27.         }
  28.         leadingZero = false;
  29.         ret.append(digit);
  30.     }
  31.     return ret.length() == 0 ? "0" : ret.toString();
  32. }

2.10 【中等】 最短无序连续子数组（581）

image.png

  1. /**
  2.  * 做一个排序，找到和原数组元素不一样的起点和终点
  3.  */
  4. public int findUnsortedSubarray(int[] nums) {
  5.     if (isSorted(nums)) {
  6.         return 0;
  7.     }
  8.     int[] numsSorted = new int[nums.length];
  9.     System.arraycopy(nums, 0, numsSorted, 0, nums.length);
  10.     Arrays.sort(numsSorted);
  11.     int left = 0;
  12.     while (nums[left] == numsSorted[left]) {
  13.         left++;
  14.     }
  15.     int right = nums.length - 1;
  16.     while (nums[right] == numsSorted[right]) {
  17.         right--;
  18.     }
  19.     return right - left + 1;
  20. }
  21. public boolean isSorted(int[] nums) {
  22.     for (int i = 1; i < nums.length; i++) {
  23.         if (nums[i] < nums[i - 1]) {
  24.             return false;
  25.         }
  26.     }
  27.     return true;
  28. }