LeetCode刷题笔记——HOT100面试题（3）

Rarit7

2019-07-13

算法

LeetCode, 栈

栈

遍历数组，发现左括号则入栈，发现右括号，弹出栈顶元素并比较。

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

155. 最小栈

使用辅助栈，保证辅助栈栈顶保存最小值。

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min;
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int x) {
        stack.push(x);
        if (min.isEmpty() || x<min.peek()) min.push(x);
        else min.push(min.peek());
    }
    
    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            min.pop();
        } else throw new RuntimeException("Stack is empty");
    }
    
    public int top() {
        if (!stack.isEmpty()) return stack.peek();
        else throw new RuntimeException("Stack is empty");
    }
    
    public int getMin() {
        if (!stack.isEmpty()) return min.peek();
        else throw new RuntimeException("Stack is empty");
    }
}

单调栈

42. 接雨水

方法一：单调栈

用栈储存高度的下标，栈内元素对应的高度不严格单调递减。遍历高度数组，当发现当前高度大于栈顶元素，表示出现“积水槽”，此时计算储水的高度h = min(height[stack.peek()], height[index]) - height[t]，水槽的宽度w = index-stack.peek()-1。

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int res = 0, index = 0;
        while (index < height.length) {
            while (!stack.isEmpty() && height[stack.peek()]<height[index]) {
                int t = stack.pop();
                if (stack.isEmpty()) break;
                int hi = Math.min(height[stack.peek()], height[index]) - height[t];
                res += hi * (index-stack.peek()-1);
            }
            stack.push(index);
            index++;
        }
        return res;
    }
}

方法二：动态规划

按列求雨水的高度。分别求出该列左右两侧的最高高度，两侧较低的值减去当前位置的高度即为雨水的高度。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i=1; i<n; i++) {
            left[i] = Math.max(height[i-1], left[i-1]);
        }
        for (int i=n-2; i>=0; i--) {
            right[i] = Math.max(height[i+1], right[i+1]);
        }
        int res = 0;
        for (int i=1; i<n-1; i++) {
            int h = Math.min(left[i], right[i]) - height[i];
            if (h>0) res+=h;
        }
        return res;
    }
}

84. 柱状图中最大的矩形

单调栈存储下标，保持栈内元素对应高度不严格单调递增。向右遍历，当遇到新的高度低于栈顶元素的高度，则可以确定此时栈顶对应高度的右边界，而左边界是弹出栈顶元素后的新栈顶（如果新栈顶与原栈顶的高度相等，不影响最终计算结果）。

在原高度数组的前后各插入一个值为0的哨兵，可以实现代码的大幅度简化：一是栈不会为空，省去每次判断栈是否为空；二是右边界必然是最低值，便于处理遍历完heights后栈内剩余的高度。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 在heights前后各插入一个0
        int[] h = new int[n+2];
        for (int i=1; i<n+1; i++) {
            h[i] = heights[i-1];
        }
        n += 2;
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);//避免判断栈是否为空
        for (int i=1; i<n; i++) {
            while (h[stack.peek()]>h[i]) {
                int height = h[stack.pop()];
                int width = i - stack.peek() - 1;
                int size = height * width;
                res = Math.max(res, size);
            }
            stack.push(i);
        }
        return res;
    }
}

85. 最大矩形

沿用第84题的思路，对每一层都可以使用单调栈计算最大矩形。这里使用一个数组记录该层对应的高度。

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if (m==0) return 0;
        int n = matrix[0].length;
        if (n==0) return 0;
        int res = 0;
        int[] heights = new int[n+2];
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                heights[j+1] = matrix[i][j]=='0'? 0: heights[j+1] + 1;
            }
            res = Math.max(res, largestRectangleArea(heights));
        }
        return res;
    }

    public int largestRectangleArea(int[] heights) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i=1; i<heights.length; i++) {
            while (heights[stack.peek()]>heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                int size = height * width;
                res = Math.max(res, size);
            }
            stack.push(i);
        }
        return res;
    }
}

739. 每日温度

使用单调栈存储气温的下标，保证栈内单调递减，一旦发现当日气温高于栈顶元素，则得到栈顶元素对应的结果值。将栈顶元素弹出，直到保持栈单调递减。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] res = new int[T.length];
        if (T.length==0) return res;
        Stack<Integer> stack = new Stack<>();
        for (int i=0; i<T.length; i++) {
            while (!stack.isEmpty() && T[stack.peek()]<T[i]) {
                int index = stack.pop();
                res[index] = i-index;
            }
            stack.push(i);
        }
        return res;
    }
}