Stack

Question 1

84. Largest Rectangle in Histogram
    Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Answer 1

Brutal force:
For loop all height. Find the first height smaller than current at left. And find the first height smaller than current at right. Then current * (right - left) is the area. Find the largest area.

Stack:
Use a stack to efficiently do the brutal force method.
The stack save the index. Smaller height save at lower position. Once a current height is larger than next height(i). Then, next height is right and the top of the stack is the left. Then pop this height in the stack. Now current height is the top of stack. if current height is larger than nexr height. Then, next height is right and the top of the stack is the left.

Question 2

456. 132 Pattern
     Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Follow up: The O(n^2) is trivial, could you come up with the O(n logn) or the O(n) solution?

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

n == nums.length
1 <= n <= 104
-109 <= nums[i] <= 109

Answer 2

很難懂。stack的想法還是不太清楚

public class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3)
            return false;
        Stack < Integer > stack = new Stack < > ();
        int[] min = new int[nums.length];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++)
            min[i] = Math.min(min[i - 1], nums[i]);
        for (int j = nums.length - 1; j >= 0; j--) {
            if (nums[j] > min[j]) {# 這種不放盡stack是因為，nums[j] == min[j]代表他一定是'132'的'1'
                while (!stack.isEmpty() &amp;&amp; stack.peek() <= min[j])#這個stack的東西比我的min[j]還要小，看來他一定是'132'的'1'，直接丟掉
                    stack.pop();
                if (!stack.isEmpty() &amp;&amp; stack.peek() < nums[j])
                    return true;
                stack.push(nums[j]);
            }
        }
        return false;
    }
}