Increase/Decrease Stack

• pop all the numbers bigger than pushing number

• We know the first smaller number on the left

while(!stack.empty() && number <= stack.peek()){
    stack.pop();
}
stack.push(number);

84 Largest Rectangle in Histogram

• Increasing Stack record the index

• 當前height <= s.peek()時開始計算面積

• 寬度計算要看s.peek()前一個index => 因為在stack沒有時可以保證之前pos的heigh都高於curHeight

• Set last height to -1 to calculate remaining ele in stack

• Time O(n), not O(n^2). Worst case pop n times, but just push one time

"""
[2,1,2] 
"""
def largestRectangleArea(self, heights: List[int]) -> int:
    stack = []
    max_rec = 0
    n = len(heights)
    
    for i in range(n+1):
        curHeight = heights[i] if i<n else -1
        while stack and curHeight < heights[stack[-1]]:
            h = heights[stack.pop()]
            # stack 會保存小於curHeight的rectangle
            w = i-stack[-1]-1 if stack else i
            max_rec = max(max_rec, h*w)
        stack.append(i)
        
    return max_rec

85 Maximum Rectangle

• Transform 2D Array to 2D accumulate histogram. If 0 in previous row then not count cuz area not connected

• Refer Largest Rectangle in Histogram above, get max area

/* 
0 0 1 0       0 0 1 0 
1 0 1 1       1 0 2 1
1 0 1 1   =>  2 0 3 2
0 0 1 0       0 0 4 0
*/

public int maximalRectangle(boolean[][] matrix) {
    if (matrix == null | matrix.length == 0 || matrix[0].length == 0){
        return 0;
    }

    // caculate accumulate histagram
    int m = matrix.length;
    int n = matrix[0].length;

    int[][] hist = new int[m][n];
    for (int i=0; i<m; i++){
        for (int j=0; j<n; j++){
            if (matrix[i][j] == false){
                hist[i][j] = 0;
            }else{
                if (i==0){ // 第一列原本就是1
                    hist[i][j] = 1;
                }else{     // accumulate histagram
                    hist[i][j] = hist[i-1][j] + 1;
                }
            }
        }
    }

    int max = 0;
    for (int i=0; i<m; i++){
        max = Math.max(max, maxHistagram(hist[i]));
    }

    return max;
}

private int maxHistagram(int[] hist){
    Stack<Integer> s = new Stack<>();
    int max = 0;
    for (int i=0; i<=hist.length; i++){
        int curHeight = (i==hist.length)? -1 : hist[i];
        while(!s.empty() && curHeight <= hist[s.peek()]){
            int h = hist[s.pop()];
            int w = s.empty()? i : i - s.peek() - 1;
            max = Math.max(max, h*w);
        }
        s.push(i);
    }
    return max;
}

496. Next Greater Element I

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

For example Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1]

• 用hashmap紀錄next greater number position

• Greedy, main a decreasing stack, 持續更新越靠右的index

• Use a stack to store the nums2[i] if it less than previous nubmers

• Otherwise, store the number to a map to query

def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
    record = {}
    stack = []
    for n in nums2:
        while stack and stack[-1] < n:
            record[stack.pop()] = n
        stack.append(n)
        
    while stack:
        record[stack.pop()] = -1
    
    res = []
    for n in nums1:
        res.append(record[n])
        
    return res

503. Next Greater Element II

Given a circular array, print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array

Input: [1,2,1]
Output: [2,-1,2]

"""
2 pass, both from back of array
first pass先拿到array increasing stack
2nd pass 紀錄答案
"""
class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        stack = []
        
        # frist pass
        for n in nums[::-1]:
            while stack and stack[-1] <= n:
                stack.pop()
            stack.append(n)
        
        # second pass
        res = []
        for n in nums[::-1]:
            while stack and stack[-1] <= n:
                stack.pop()
            if stack:
                res.append(stack[-1])
            else:
                res.append(-1)
            stack.append(n)
                
        return res[::-1]

739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature

For example T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]

• Use a stack

"""
Traverse from back, stack store index and num in increasing order
While loop compare the cur num and stack[-1] num, pop the smaller num than itself
"""
def dailyTemperatures(self, T: List[int]) -> List[int]:
    n = len(T)
    stack = []
    res = []
    
    for i in range(n-1, -1, -1):
        while stack and T[stack[-1]] <= T[i]:
            stack.pop()
        if stack:
            res.append(stack[-1] - i)
        else:
            res.append(0)
        stack.append(i)
            
    return res[::-1]

239 Sliding Window Max

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 

• Maintain a Dequeue in decreasing

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    if not k or not nums: return []
    if k == 1: return nums
    
    
    # Maintain a decreasing queue which only k range from current idx
    # q[0] is the current max
    def helper(q, idx):    
        # if current max is from previous k 
        if q and idx>=k and q[0] == nums[idx-k]:
            q.pop(0)
            
        # evict numbers on idx smaller than current idx
        while q and nums[idx] > q[-1]:
            q.pop()
        q.append(nums[idx])
        
    q = []
    for i in range(k):
        helper(q, i)
        
    ans = [q[0]]
    
    for i in range(k,len(nums)):
        helper(q, i)
        ans.append(q[0])
    return ans

480. Sliding Window Median

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

"""
Maintain a sorted array
"""
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
    ans = []
    arr= []
    
    def helper(idx, arr):
        if idx >= k:
            delete_idx = bisect.bisect_left(arr, nums[idx-k])
            arr.pop(delete_idx)
        insert_idx = bisect.bisect(arr, nums[idx])
        arr.insert(insert_idx, nums[idx])
        
    def getMedium(arr):
        n = len(arr)
        if n%2:
            return arr[n//2]
        else:
            return (arr[n//2-1] + arr[n//2])/2
    
    for i in range(k):
        helper(i, arr)
        
    ans.append(getMedium(arr))
    
    for i in range(k, len(nums)):
        helper(i, arr)
        ans.append(getMedium(arr))    
    return ans

862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

1. 這題跟209的差異是num可能為負數

2. 用一個dequeue紀錄 sum and index, dequeue in increasing order by sum

3. Update if we can find total - sum >= k, and kind updating to shorten the distant

4. Explain

def shortestSubarray(self, A: List[int], K: int) -> int:       
    q = [[-1, 0]] # [index, total]
    total = 0        
    ans = float('inf')

    for i, n in enumerate(A):
        total += n            
        while q and total - q[0][1] >= K:
            ans = min(ans, i - q[0][0])
            q.pop(0)
        
        while q and total <= q[-1][1]:
            q.pop()
        q.append([i, total])
        
    return ans if ans != float('inf') else -1

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Input: num = "1432219", k = 3
Output: "1219"
Input: num = "10", k = 2
Output: "0"

'''
greedy + stack
Remove the nums before cur num which are greater then cur num
'''
def removeKdigits(self, num: str, k: int) -> str:
    stack = []
    for n in num:
        while k > 0 and stack and stack[-1] > n:
            stack.pop()
            k -= 1
        stack.append(n)
        
    if k:
        stack = stack[:-k]
                       # if '0' in head   # if ans is empty
    return ''.join(stack).lstrip('0') or '0'