Trapping rain water

• approach i: two pointer
  • pick boundaries, start end
  • find the lower boundaries, height[start] height[end]
  • calculate the water trapped by lower boundaries, while till height[i] > min(height[start], height[end])
  • replace boundary
  • https://discuss.leetcode.com/topic/62718/how-to-get-the-solution-to-2-d-trapping-rain-water-problem-from-1-d-case
• approach ii: stack, similar to rectangle

public class Solution {
    public int trapRainWater(int[] height) {
        // write your code here

        if (height == null || height.length == 0) {
            return 0;
        }
        int start = 0;
        int end = height.length - 1;
        int area = 0;
        while (start < end) {
            int left = height[start];
            int right = height[end];
            if (left < right) {
                while (start < end && height[start] <= left) {
                    area += left - height[start];
                    start++;
                }
            } else {
                while (start < end && height[end] <= right) {
                    area += right - height[end];
                    end--;
                }
            }
        }
        return area;
    }
}

class Solution {
    public int trap(int[] A) {
        if (A==null) return 0;
        Stack<Integer> s = new Stack<Integer>();
        int i = 0, maxWater = 0, maxBotWater = 0;
        while (i < A.length){
            if (s.isEmpty() || A[i]<=A[s.peek()]){
                s.push(i++);
            }
            else {
                int bot = s.pop();
                maxBotWater = s.isEmpty()? // empty means no il
                0:(Math.min(A[s.peek()],A[i]) - A[bot]) * (i-s.peek()-1);
                maxWater += maxBotWater;
            }
        }
        return maxWater;
    }
}

Trapping rain water ii:

• https://www.youtube.com/watch?v=cJayBq38VYw
• https://discuss.leetcode.com/topic/62718/how-to-get-the-solution-to-2-d-trapping-rain-water-problem-from-1-d-case

class Solution {
    public int trapRainWater(int[][] height) {
        int m = height.length;
        if (m == 0) return 0;
        int n = height[0].length;
        if (n == 0) return 0;
        int[][] visited = new int[m][n];

        PriorityQueue<Cell> pq = new PriorityQueue<>(m*n, (c1, c2) -> c1.height - c2.height);

        for (int i = 0; i < m; i++) {
            pq.offer(new Cell(i, 0, height[i][0]));
            pq.offer(new Cell(i, n-1, height[i][n-1]));
            visited[i][0] = 1;
            visited[i][n-1] = 1;
        }

        for (int j = 0; j < n; j++) {
            pq.offer(new Cell(0, j, height[0][j]));
            pq.offer(new Cell(m-1, j, height[m-1][j]));
            visited[0][j] = 1;
            visited[m-1][j] = 1;
        }

        int[] dx = new int[] {0,-1,0,1};
        int[] dy = new int[] {-1,0,1,0};
        int rst = 0;
        while (!pq.isEmpty()) {
            Cell curr = pq.poll();
            for (int i = 0 ; i < 4; i++) {
                int nx = curr.x + dx[i];
                int ny = curr.y + dy[i];
                if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || visited[nx][ny] == 1) continue;
                rst += Math.max(0, curr.height - height[nx][ny]);
                pq.offer(new Cell(nx, ny, Math.max(curr.height, height[nx][ny])));
                visited[nx][ny] = 1;
            }
        }
        return rst;        
    }

    class Cell {
        int x;
        int y;
        int height;
        public Cell(int x, int y, int height) {
            this.x = x;
            this.y = y;
            this.height = height;
        }
    }
}

min stack:

// version 1:
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            minStack.push(Math.min(number, minStack.peek()));
        }
    }

    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

// version 2, save more space. but space complexity doesn't change.
public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty())
            minStack.push(number);
        else {
        // 这里考虑的相等的情况也会继续push
        if (minStack.peek() >= number)
            minStack.push(number);
        }
    }

    public int pop() {
        if (stack.peek().equals(minStack.peek()) ) 
            minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

largest rectangle in histogram

public class Solution {
    public int largestRectangleArea(int[] height) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i <= height.length; i++) { // use <=, because in the end need to purge stack again to evaluate the area, so combine those two cases. 

            int curr = height.length == i ? -1 : height[i];

            while (!stack.isEmpty() && height[stack.peek()] >= curr) {
                int h = height[stack.pop()];
                int w = stack.isEmpty() ? i : (i-stack.peek()-1);
                int area = h * w;
                max = Math.max(max, area);
            }
            stack.push(i);
        }
        return max;
    }
}

maximal rectangle

• reduce dimension (aggregate rows) to largest rectangle problem

public class Solution {
    public int maximalRectangle(boolean[][] matrix) {
        // Write your code here
        if (matrix.length < 1) return 0;
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;
        int[][] height = new int[n][m];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0)
                    height[i][j] = ((matrix[i][j] == true) ? 1 : 0);
                else
                    height[i][j] += ((matrix[i][j] == true) ? height[i-1][j] + 1 : 0);
            }
        }

        int answer = 0;
        for (int i = 0; i < n; ++i) {
            Stack<Integer> S = new Stack<Integer>();  
            for (int j = 0; j <= m; j++) {
                int curr = (j == m ? -1 : height[i][j]);
                while (!S.empty() && curr <= height[i][S.peek()]) {
                    int h = height[i][S.pop()];
                    int w = S.empty()? j : j-S.peek()-1;
                    answer = Math.max(answer, h*w);
                }
                S.push(j);
            }
        }
        return answer;
    }
}

maximal square

• dp

public int maxSquare(int[][] matrix) {
        // write your code here
        int ans = 0;
        int n = matrix.length;
        int m;
        if(n > 0)
            m = matrix[0].length;
        else 
            return ans;
        int [][]res = new int [n][m];
        for(int i = 0; i < n; i++){
            res[i][0] = matrix[i][0];
            ans = Math.max(res[i][0] , ans);
            for(int j = 1; j < m; j++) {
                if(i > 0) {
                    if(matrix[i][j] > 0) {
                        res[i][j] = Math.min(res[i - 1][j],Math.min(res[i][j-1], res[i-1][j-1])) + 1;
                    } else {
                        res[i][j] = 0;
                    }

                }
                else {
                    res[i][j] = matrix[i][j];
                }
                ans = Math.max(res[i][j], ans);
            }
        }
        return ans*ans;
    }

sliding window maximum

• cf sliding window median: using two heaps
• use deque
  • main idea: only keep promising candidates and maintain related index order
  • when enqueue, popLast() all numbers that are smaller than coming element, addLast() new elements
  • when dequeue, when the element exist, popFirst()
  • get result: add peekFirst()

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        ArrayList<Integer> rst = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            inQueue(nums[i], deque);
            if (i - k >= 0) {
                outQueue(nums[i-k], deque);
            }
            if (i + 1 - k >= 0) {
                rst.add(deque.peekFirst());
            }
        }
        return rst;
    }

    private void inQueue(int num, ArrayDeque<Integer> deque) {
        while (!deque.isEmpty() && num > deque.peekLast()) {
            deque.pollLast();
        }
        deque.addLast(num);
    }

    private void outQueue(int num, ArrayDeque<Integer> deque) {
        if (deque.peekFirst() == num) {
            deque.pollFirst();
        }
    }
};