栈， 单调栈

单调栈例题

有N个人，顺次排列，他们的身高分别为H[i]，每个人向自己后方看，他能看到的人是在他后面离他最近的且比他高的人。请依次输出每个人能看到的人的编号Next[i]，如果他后面不存在比他高的人，则输出-1。

想找 "从当前元素向某一方向的第一个 (大于 / 小于) 自己的元素"，就要靠单调栈来维护单调性，对应的是 (递减 / 递增)。

public class Main {

    public static int[] getHeight(int[] heights){
        int n = heights.length;
        int[] arr = new int[n];

        // Stack stores index of people
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            while(!stack.isEmpty() && heights[stack.peek()] <= heights[i]){
                arr[stack.pop()] = i;
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            arr[stack.pop()] = -1;
        }

        return arr;
    }

    public static void main(String[] args){
        int[] heights1 = {3,2,5,6,1,2};
        int[] heights2 = {1,2,3,4,5,6};
        int[] heights3 = {6,5,4,3,2,1};
        int[] heights4 = {6,1,3,4,2,5};

        int[] arr = getHeight(heights4);
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + "  ");
        }
    }
}

Largest Rectangle in Histogram

顺着上一题的思路，这题比较暴力的解法可以分为三步：

• 从左向右扫，寻找对于每个元素，往右能看到的最远距离；

• 从右向左扫，寻找对于每个元素，往左能看到的远距离；

• 把两个 arr[] 的结果综合起来，就是从每个位置出发能构造的最大 rectangle.

速度非常慢，只超过了 1.27% ，因为常数项更大。虽然时间复杂度是 O(n)，但是用了 three-pass 才搞定。如果说这种解法有什么优点，就是比较好理解。。是单调栈非常简单直接的应用方式，不加任何 trick.

public class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] right = findToRight(heights);
        int[] left = findToLeft(heights);

        int max = 0;
        for(int i = 0; i < heights.length; i++){
            max = Math.max(max, (right[i] - left[i] + 1) * heights[i]);
        }

        return max;
    }

    private int[] findToRight(int[] heights){
        int[] right = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < heights.length; i++){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                right[stack.pop()] = i - 1;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            right[index] = heights.length - 1;
        }
        return right;
    }

    private int[] findToLeft(int[] heights){
        int[] left = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = heights.length - 1; i >= 0; i--){
            while(!stack.isEmpty() && heights[stack.peek()] > heights[i]){
                left[stack.pop()] = i + 1;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int index = stack.pop();
            left[index] = 0;
        }
        return left;
    }
}

Increasing Triplet Subsequence

用 LIS 的角度理解的话这题就是无脑套模板。。

不过题目要求 O(n) 时间 O(1) 空间，就得另外动动脑筋了。

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int index = 0;
        for(int i = 1; i < n; i++){
            int pos = binarySearch(dp, 0, index, nums[i]);
            if(pos > index){
                dp[pos] = nums[i];
                index = pos;
                if(index + 1 >= 3) return true;
            }
            dp[pos] = Math.min(dp[pos], nums[i]);
        }
        return false;
    }

    private int binarySearch(int[] nums, int start, int end, int target){
        int left = start;
        int right = end;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid;
            } else {
                right = mid;
            }
        }

        if(target <= nums[left]) return left;
        if(target > nums[right]) return right + 1;

        return right;
    }
}

通过观察这题的具体性质，我们发现在这里我们所谓的 "单调栈" 长度其实是固定的，就是3，等于3了直接返回就行。

因为 3 非常小，我们只需要存两个值，分别代表着单调栈的第一个和第二个位置；当我们碰到第三个位置的情况，就可以返回 true 了。

这个解法的思想也可以推广到任意 k ，k比较小或者为常数的情况，毕竟对于常数 k ，O(k) = O(1).

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums == null || nums.length < 3) return false;
        int n = nums.length;

        int num1 = Integer.MAX_VALUE;
        int num2 = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            if(nums[i] <= num1){
                num1 = nums[i];
            } else if(nums[i] <= num2){
                num2 = nums[i];
            } else {
                return true;
            }
        }

        return false;
    }
}

Russian Doll Envelopes

[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]

这题试着用 LIS 的写法思路写了一下，然而卡在了这个 test case 上。

• 因为这题，元素之间不存在绝对的大小，不能直接用两个 tuple 去比较，进行 binary search.

• 两个 tuple [4,300] 和 [5,250] 之间，按理可以说 [4, 300] 更小，但是有可能最优解是由 [5,250] 选出来的。

正解的流程：

• 按 [w, h] 中的 w 升序排序；

• 如果 w 相等，则按照 h 的降序排序(重要！！！)

• 后面的就和一维 LIS 一样，只考虑 h 的维度做 LIS 就行了。

难点在于，为什么这么做是正确的？

• 不难看出对于同一个 w 的楼层，我们不能按 h 升序排列，因为会延长自身，导致在同一个 w 上多次套用。

• 因此对于同一 w 的情况， 要按照 h 降序排列

• 这样当我们看到一个更大的 h 时，我们可以确定，这一定是一个新的 w，而且根据原来排序的单调性，一定是一个比单调栈内元素都大的新 w，可以套上。

• 同时对于单调栈中的任意 h，如果 binary search 之后的位置 pos 位于中间，它一定可以套在 pos 之前的所有信封上。

速度超过 87.50%，还不错。

public class Solution {
    private class MyComparator implements Comparator<int[]>{
        public int compare(int[] a, int[] b){
            if(a[0] != b[0]) return (a[0] < b[0]) ? -1: 1;
            else return (a[1] < b[1]) ? 1: -1;
        }
    }

    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes == null || envelopes.length == 0) return 0;
        Arrays.sort(envelopes, new MyComparator());
        int n = envelopes.length;
        int[] dp = new int[n];
        dp[0] = envelopes[0][1];
        int index = 0;

        for(int i = 1; i < n; i++){
            int pos = binarySearch(dp, 0, index, envelopes[i][1]);
            if(pos > index){
                dp[pos] = envelopes[i][1];
                index = pos;
            }
            dp[pos] = Math.min(dp[pos], envelopes[i][1]);
        }
        return index + 1;
    }

    private int binarySearch(int[] dp, int start, int end, int height){
        int left = start;
        int right = end;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;

            if(height < dp[mid]){
                right = mid;
            } else {
                left = mid;
            }
        }
        if(height <= dp[left]) return left;
        if(height > dp[right]) return right + 1;

        return right;
    }
}

Maximal Rectangle