有效的括号#20（简单）

https://leetcode.cn/problems/valid-parentheses/

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         //法一:哈希表+栈.时间复杂度O(n),空间复杂度O(n)
  4.         int n = s.length();
  5.         if (n % 2 == 1) return false;
  6.         Map<Character, Character> pairs = new HashMap<>();
  7.         pairs.put(')', '(');
  8.         pairs.put(']', '[');
  9.         pairs.put('}', '{');
  10.         Deque<Character> stack = new LinkedList<>();
  11.         for (int i = 0; i < n; i++) {
  12.             char ch = s.charAt(i);
  13.             if (pairs.containsKey(ch)) {
  14.                 if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
  15.                     return false;
  16.                 }
  17.                 stack.pop();
  18.             } else {
  19.                 stack.push(ch);
  20.             }
  21.         }
  22.         return stack.isEmpty();
  23.     }
  24. }
  25. //==================================================
  26. class Solution {
  27.     public boolean isValid(String s) {
  28.         //法二:ASCII码+栈.时间复杂度O(n),空间复杂度O(n)
  29.         int n = s.length();
  30.         if (n % 2 == 1) return false;
  31.         Deque<Character> stack = new LinkedList<>();
  32.         stack.push(s.charAt(0));
  33.         for (int i = 1; i < n; i++) {
  34.             char ch = s.charAt(i);
  35.             if (stack.isEmpty()) {
  36.                 stack.push(ch);
  37.             } else if (ch - stack.peek() == 1 || ch - stack.peek() == 2) {
  38.                 stack.pop();
  39.             } else {
  40.                 stack.push(ch);
  41.             }
  42.         }
  43.         return stack.isEmpty();
  44.     }
  45. }

最长有效括号#32（困难）

https://leetcode.cn/problems/longest-valid-parentheses/

  1. class Solution {
  2.     public int longestValidParentheses(String s) {
  3.         //法二:栈.时间复杂度O(n),空间复杂度O(n)
  4.         int maxans = 0;
  5.         Deque<Integer> stack = new LinkedList<>();
  6.         stack.push(-1);
  7.         for (int i = 0; i < s.length(); i++) {
  8.             if (s.charAt(i) == '(') {
  9.                 stack.push(i);
  10.             } else {
  11.                 stack.pop();
  12.                 if (stack.isEmpty()) {
  13.                     stack.push(i);
  14.                 } else {
  15.                     maxans = Math.max(maxans, i - stack.peek());
  16.                 }
  17.             }
  18.         }
  19.         return maxans;
  20.     }
  21. }

接雨水#42（困难）

https://leetcode.cn/problems/trapping-rain-water/

  1. public int trap(int[] height) {
  2.     //该解法超时了❌
  3.     //法一:按行求.求出每一行接水量，然后累加
  4.     //时间复杂度O(m*n),m是最大高度,n是数组长度。约等于n^2所以会超时。
  5.     //空间复杂度O(1)。
  6.     //当出现第一个高度大于等于行数的开始更新，
  7.     //之后高度小于行数则接水量+1，直到高度大于等于行数则加入到总量中。
  9.     //总共水量sum
  10.     int sum = 0;
  11.     //先求出最大高度，也即是行数，也就是最外层循环的次数
  12.     int maxHeight = 0;
  13.     for (int i = 0; i < height.length; i++) {
  14.         maxHeight = maxHeight > height[i] ? maxHeight : height[i];
  15.     }
  17.     //最外层循环，求每一层的积水量
  18.     for (int i = 1; i <= maxHeight; ++i) {
  19.         //标记是否开始更新temp
  20.         boolean isStart = false;
  21.         int temp = 0;
  22.         for (int j = 0; j < height.length; ++j) {
  23.             if (isStart && height[j] < i) {
  24.                 temp++;
  25.             }
  26.             if (height[j] >= i) {
  27.                 sum += temp;
  28.                 temp = 0;
  29.                 isStart = true;
  30.             }
  31.         }
  32.     }
  33.     return sum;
  34. }
  36. public int trap(int[] height) {
  37.     //法二:按列求。时间复杂度O(n^2),空间复杂度O(1)
  38.     int sum = 0;
  39.     //最两边的列是没有办法接到水的
  40.     for (int i = 1; i < height.length - 1; i++) {
  41.         //找出左边的最高棒子
  42.         int maxLeft = 0;
  43.         for (int j = i - 1; j >= 0; --j) {
  44.             if (height[j] > maxLeft) {
  45.                 maxLeft = height[j];
  46.             }
  47.         }
  48.         //找出右边最高的棒子
  49.         int maxRight = 0;
  50.         for (int j = i + 1; j < height.length; ++j) {
  51.             //本来想三目运算符一句话写完。但是每一次三目运算符都有赋值运算。还是觉得这样更好
  52.             if (height[j] > maxRight) {
  53.                 maxRight = height[j];
  54.             }
  55.         }
  56.         //找出两端最小值
  57.         int minHeight = Math.min(maxLeft, maxRight);
  58.         if (minHeight > height[i]) {
  59.             sum = sum + (minHeight - height[i]);
  60.         }
  61.     }
  62.     return sum;
  63. }
  65. public int trap(int[] height) {
  66.     //法三:动态规划。利用两个数组记录当前列的左边最高和右边最高。
  67.     //时间复杂度O(n),空间复杂度O(n)
  68.     int sum = 0;
  69.     int n = height.length;
  70.     int[] maxLeftArray = new int[n];
  71.     int[] maxRightArray = new int[n];
  72.     //求出左边最高列数组
  73.     for (int i = 1; i < n; i++) {
  74.         maxLeftArray[i] = Math.max(maxLeftArray[i - 1], height[i - 1]);
  75.     }
  76.     //求出右边最高列的数组
  77.     for (int i = n - 2; i > 0; --i) {
  78.         maxRightArray[i] = Math.max(maxRightArray[i + 1], height[i + 1]);
  79.     }
  80.     for (int i = 1; i < n - 1; ++i) {
  81.         int minHeight = Math.min(maxLeftArray[i], maxRightArray[i]);
  82.         if (minHeight > height[i]) {
  83.             sum += minHeight - height[i];
  84.         }
  85.     }
  86.     return sum;
  87. }
  89. public int trap(int[] height) {
  90.     //法四:双指针。时间复杂度O(n),空间复杂度O(1)
  91.     int n = height.length;
  92.     int sum = 0;
  93.     int maxLeft = 0;
  94.     int maxRight = 0;
  95.     int left = 1;
  96.     int right = n - 2;//加右指针进去
  97.     for (int i = 1; i < n - 1; i++) {
  98.         //对于左边，左边最高是可信的，对于右边，右边最高是可信的
  99.         //所以左边最高小于右边最高时就可以确定自己能装多少水了
  100.         if (height[left - 1] < height[right + 1]) {
  101.             //从左到右更新
  102.             maxLeft = Math.max(maxLeft, height[left - 1]);
  103.             int min = maxLeft;
  104.             if (min > height[left]) {
  105.                 sum = sum + (min - height[left]);
  106.             }
  107.             left++;
  108.         } else {
  109.             //从右到左更新
  110.             maxRight = Math.max(maxRight, height[right + 1]);
  111.             int min = maxRight;
  112.             if (min > height[right]) {
  113.                 sum = sum + (min - height[right]);
  114.             }
  115.             right--;
  116.         }
  117.     }
  118.     return sum;
  119. }
  121. public int trap(int[] height) {
  122.     //法五:单调栈。时间复杂度O(n),空间复杂度O(n)
  123.     int sum = 0;
  124.     Deque<Integer> stack = new LinkedList<>();
  125.     int n = height.length;
  126.     for (int i = 0; i < n; ++i) {
  127.         while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
  128.             int top = stack.pop();
  129.             if (stack.isEmpty()) {
  130.                 break;
  131.             }
  132.             int left = stack.peek();
  133.             int currWidth = i - left - 1;
  134.             int currHeight = Math.min(height[left], height[i]) - height[top];
  135.             sum += currWidth * currHeight;
  136.         }
  137.         stack.push(i);
  138.     }
  139.     return sum;
  140. }

简化路径#71（中等）

https://leetcode.cn/problems/simplify-path/

class Solution {
    public String simplifyPath(String path) {
        //法一：栈。时间复杂度O(n),空间复杂度O(n)
        //注意Deque的push和pop操作都是操作的头，所以只能用queue的api
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) stack.pollLast();
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuilder ans = new StringBuilder();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
        }
        return ans.toString();
    }
}

柱状图中最大的矩形#84（困难）

https://leetcode.cn/problems/largest-rectangle-in-histogram/

public int largestRectangleArea(int[] heights) {
    //该解法超时了❌
    //法一:枚举宽度的暴力解法.时间复杂度O(n^2),空间复杂度O(1)
    int length = heights.length;
    int maxArea = 0;
    for (int i = 0; i < length; ++i) {
        int minHeight = Integer.MAX_VALUE;
        for (int j = i; j < length; ++j) {
            minHeight = Math.min(minHeight, heights[j]);
            maxArea = Math.max(maxArea, minHeight * (j - i + 1));
        }
    }
    return maxArea;
}
//===============================================================
public int largestRectangleArea(int[] heights) {
    //该解法超时了❌
    //法二:枚举高度暴力解法.时间复杂度O(n^2),空间复杂度O(1)
    int length = heights.length;
    int maxArea = 0;
    for (int mid = 0; mid < length; mid++) {
        int height = heights[mid];
        int left = mid;
        int right = mid;
        while (left - 1 >= 0 && heights[left-1] >= height) {
            --left;
        }
        while (right + 1 < length && heights[right+1] >= height) {
            ++right;
        }
        maxArea = Math.max(maxArea, height * (right - left + 1));
    }
    return maxArea;
}
//===============================================================
class Solution {
    public int largestRectangleArea(int[] heights) {
        //法三：单调栈+两次遍历.时间复杂度O(n),空间复杂度O(n)
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        mono_stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}
//===============================================================
class Solution {
    public int largestRectangleArea(int[] heights) {
        //法四：单调栈+一次遍历.时间复杂度O(n),空间复杂度O(n)
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        Deque<Integer> mono_stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}