[LeetCode]No739 Daily Temperature 每日温度 & No42 Trapping Rain Water 接雨水

No.739 Daily Temperature 每日温度

Brute Force 暴力法

从左到右用双重循环来找到第一个比当天温度大的值

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res = new int[len];
        if (len == 0) return res;

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (T[j] > T[i]) {
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }
}

时间复杂度为O(N^2)

对暴力法的优化

由于每天都需得到一解，至少遍历一次数组，目前的时间复杂度为O(N)，那么在确定某天后，减少其对数组的二次遍历。答案为：从右往左遍历,这样做的好处是，在当前位置k与k+1比较，若T[k] > T[k + 1]，可以根据 result[k+1]的值，直接找比k+1大的值再次比较，而不用与比k+1小的值比较。

其中有递归的思想，最后一天没有比其温度更高的一天，所以一开始就确定为0，再向前推导，前面的值的确定基于后面的值。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res = new int[len];
        if (len == 0) return res;

        for (int i = len - 1; i >= 0; i--) {
            if (i == len - 1) res[i] = 0;
            else {
                for (int j = i + 1; j < len; ) {
                    if (T[j] > T[i]) {
                        res[i] = j - i;
                        break;
                    }
                    else if (res[j] == 0) { // 容易忽略的条件
                        res[i] = 0;
                        break;
                    }
                    j = j + res[j];
                }
            }
        }
        return res;
    }
}

单调栈

维护一个 元素递减 的栈，留在栈里的元素意味着 还未匹配到比当天温度高的日子。每当遍历一个新的元素（即新的一天），比较栈顶，如果比栈顶元素大，意味着匹配成功，栈顶元素出栈，result[栈顶元素的序号] = 序号差。直到比较到栈空或者栈顶元素比当前元素温度高。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int len = T.length;
        int[] res = new int[len];
        if (len == 0) return res;
        Stack<Integer> decreaseStack = new Stack<>();

        for (int i = 0; i < len; i++) {
            while (!decreaseStack.isEmpty() && T[i] > T[decreaseStack.peek()]) {
                int idx = decreaseStack.pop();
                res[idx] = i - idx;
            }
            decreaseStack.push(i);
        }
        return res;
    }
}

No.42 Trapping Rain Water 接雨水

动态规划的思路

遍历每一列，当前高度为current，分别找到其左侧和右侧的最高值maxLeft和maxRight，按木桶原理，找到shorterWall = Math.min(maxLeft, maxRight)，若shorterWall <= current，则接不到雨水，当前列存储的volume = 0。当且仅当 shorterWall > current，可以接到雨水，且volume = shorterWall - current。

用到动态规划思想的是leftMax和rightMax两个数组。

public int trap(int[] height) {
        int len = height.length;
        int res = 0;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        // 定义两个数组，分别存储 current 元素左侧的最大值和右侧的最大值
        for (int i = 0; i < len; i++) {
            if (i == 0) leftMax[i] = 0;
            else {
                leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
            }
        }
        for (int j = len - 1; j >= 0; j--) {
            if (j == len - 1) rightMax[j] = 0;
            else {
                rightMax[j] = Math.max(rightMax[j + 1], height[j + 1]);
            }
        }
        for (int k = 0; k < len; k++) {
            int shorterWall = Math.min(leftMax[k], rightMax[k]);
            if (shorterWall > height[k]) {
                res += shorterWall - height[k];
            }
        }
        return res;
    }

时间复杂度为O(N)

双指针法优化动态规划

因为上面的动态规划用到了两个数组leftMax和rightMax，而其值只在遍历的时候用了一次，考虑是否能用一个变量代替数组。当从左到右遍历时

public int trap(int[] height) {
        int len = height.length;
        int res = 0;
        int[] rightMax = new int[len];
        int leftMax = 0; // leftMax数组用一个变量代替

        for (int j = len - 1; j >= 0; j--) {
            if (j == len - 1) rightMax[j] = 0;
            else {
                rightMax[j] = Math.max(rightMax[j + 1], height[j + 1]);
            }
        }
        for (int k = 1; k < len - 1; k++) {
            leftMax = Math.max(leftMax, height[k - 1]);
            int shorterWall = Math.min(leftMax, rightMax[k]);
            if (shorterWall > height[k]) {
                res += shorterWall - height[k];
            }
        }
        return res;
    }

这种方法未能替换rightMax，那么如何将rightMax数组也变成一个变量呢？

左右开弓双指针法

从左往右遍历时，左边的leftMax是可信的；反之，从右往左遍历，右边的rightMax是可信的。一个关键条件是，如果leftMax < rightMax，那么不用在意rightMax是否可信，用leftMax求解即可。所以，设置判断条件，当leftMax <= rightMax，代码与上面的思路相仿；当rightMax < leftMax，此时rightMax是可信的，变成从右向左遍历。

变量：

leftMax: 左侧最大值
rightMax: 右侧最大值
left: 从左到右遍历当前遍历的元素
right: 从右到左遍历当前遍历的元素

public int trap(int[] height) {
        int len = height.length;
        int res = 0;
        if (len == 0) return 0;
        int left = 1, right = len - 2;
        int leftMax = height[0], rightMax = height[len - 1];

        while (left <= right) {
            if (leftMax <= rightMax) {
                if (leftMax > height[left]) {
                    res += leftMax - height[left];
                }
                else {
                    leftMax = height[left];
                }
                left++;
            }
            else {
                if (rightMax > height[right]) {
                    res += rightMax - height[right];
                }
                else {
                    rightMax = height[right];
                }
                right--;
            }
        }
        return res;
    }

单调栈法

单调递减栈也相当于维护了leftMax，若当前高度大于栈顶，则找到了右边高的墙，出现了凹槽，可以储水。循环直到当前高度小于等于栈顶或栈为空。

public int trap(int[] height) {
        int res = 0;
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < height.length; i++) {
            while (!deque.isEmpty() && height[i] > height[deque.peek()]) { // 可能存在凹槽的条件
                int lowest = deque.pop();
                if (deque.isEmpty()) { // 如果没有更高点，则不能储水
                    break;
                }
                int distance = i - deque.peek() - 1;
                int h = Math.min(height[i], height[deque.peek()]) - height[lowest];
                res += distance * h;
            }
            deque.push(i);
        }
        return res;
    }