Leetcode stack problem

单调栈

Find the first element on the left which is larger than itself.

The most straight forward idea is to compare the current element with the left element in the list one by one. But soon we found that it is not the efficient solution. For example, you have a list [1,4,2,3,5]. When you compare the element 5 with 3, you found 5 > 3, then you proceed to the next element 2. But when you set the position of 3, you have already do the comparison 3 > 2. So we do not need to do the comparison 5 > 2, which could save the computation time if the list is much larger.

So, we apply the trick of the decreasing stack. The idea is to keep a temporary list and the elements in this list are in decreasing order. At the beginning, the decreasing stack is empty. Then, we loop through the list, and for each element, we compare the element with the top element in the decreasing stack. If larger, then pop the top element out, and do it again until the decreasing stack is empty or it encouter the top elment which is larger than itself. If empty, it means no other element is larger than it, otherwise, output the element which is larger than it. Finally, push it into the decreasing stack.

# 单调递减栈实现返回列表中左边第一个比自身大的元素的值
def decreasing_stack(nums):
    index=[-1]
    stack=[nums[0]]
    for i in range(1,len(nums)):
        while stack and nums[i]>=stack[-1] :
            stack.pop()
        if stack:
            index.append(stack[-1])
        else:
            index.append(-1)
        stack.append(nums[i])
    return index
a=[4,2,3,5]
decreasing_stack(a)

# 返回index
def decreasing_stack_return_index(nums):
    index=[-1]
    stack=[0]
    for i in range(1,len(nums)):
        while stack and nums[i]>=nums[stack[-1]] :
            stack.pop()
        if stack:
            index.append(stack[-1])
        else:
            index.append(-1)
        stack.append(i)
    return index
a=[4,2,3,2]
decreasing_stack_return_index(a)

[-1, 0, 0, 2]

42. Trapping Rain Water

这道题感觉不是十分好想，需要维持一个stack来进行操作，当遇到新加的元素比栈顶元素大的时候，我们就要比较之前的元素，如果栈里面是有一个，则不能形成坑，continue；不然就比较之前的元素和当前的最小值，减去高度。我们的做法是，遍历高度，如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意我们不直接把高度压入栈，而是把坐标压入栈，这样方便我们在后来算水平距离。当我们遇到比栈顶高度大的时候，就说明有可能会有坑存在，可以装雨水。此时我们栈里至少有一个高度，如果只有一个的话，那么不能形成坑，我们直接跳过，如果多余一个的话，那么此时把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界，只要取二者较小的，减去坑的高度，长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量啦,重复此操作直至当前高度小于等于栈顶高度，把当前高度压入栈

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack = []
        i = 0
        size = len(height)
        res = 0
        while i < size:
            if not stack or height[i] <= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                top = stack.pop()
                if not stack:
                    continue
                else:
                    res += (min(height[i], height[stack[-1]]) - height[top]) * (i - stack[-1] -1) # height * width
        return res

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.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

So let’s consider the most straightforward method. For each element in nums2, we compare it with its right elements one by one until it finds the first element which is larger than it. But let’s consider a small unit [2,1,3]. Notice that we first compare 2 > 1, and then compare 2 < 3, and we finish element 2. Then we move on element 1. This time, we already know 1 < 2, and the first element larger than 2 is 3, so it means we do not need to compare 1 with 3, which the algorithm still does. So, this brute-force method is not efficient.

A decreasing stack is used in this situation. The stack will keep the index of the element in the list. Consider the simple unit L = [2,1,3]. First, the stack is empty. Then the stack becomes [0], [0,1]. When L[2] comes in, it compares L[2] > L[1], so the next greater element of L[1] is L[2]. Then compare L[2] and L[0], we know the next greater element of L[0] is L[2]. Just like this.

def next_greater_element(a,b):
    stack=[b[0]]
    res={}
    for i in range(1,len(b)):
        while stack and b[i]>stack[-1]:
            res[stack.pop()]=b[i]
        stack.append(b[i])
    while stack:
        res[stack.pop()]=-1
    newRes=[]
    for i in a:
        newRes.append(res[i])
    return newRes
nums1 = [4,1,2]
nums2 = [1,3,4,2]
print(next_greater_element(nums1,nums2))
nums1=[1,2,1]
nums2=[1,2,1]
print(next_greater_element(nums1,nums2))

[-1, 3, -1]
[-1, -1, -1]

739. Daily Temperatures

用一个单调递减栈完事

def warmer_weather(x):
    stack=[0]
    res={}
    for i in range(1,len(x)):
        while stack and x[i]>x[stack[-1]]:
            res[stack.pop()]=i
        stack.append(i)
    while stack:
        temp=stack.pop()
        res[temp]=temp
    newRes=[]
    for i in range(len(x)):
        newRes.append(res[i]-i)
    return newRes
a=[73, 74, 75, 71, 69, 72, 76, 73]
warmer_weather(a)

[1, 1, 4, 2, 1, 1, 0, 0]

503. Next Greater Element II

def next_greater_element(x):
    res=[-1]*len(x)
    stack=[0]
    for i in range(1,len(x)*2):
        while stack and x[i%len(x)]>x[stack[-1]]:            
            res[stack.pop()]=x[i%len(x)]    
        if i<=len(x)-1:
            stack.append(i%len(x))
    return res
a=[1,2,1]
print(next_greater_element(a))

[2, -1, 2]

316. Remove Duplicate Letters

class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        dic = dict()
        for char in s:
            dic[char] = dic.get(char, 0) + 1

        for char in s:
            dic[char] -= 1
            if char in stack:
                continue
            else:
                while stack and ord(char) < ord(stack[-1]) and dic[stack[-1]] > 0:
                    stack.pop()
            stack.append(char)
        return "".join(stack)

84. Largest Rectangle in Histogram

def largestRectangleArea( heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        stack = []
        for i in range(len(heights)+1):
            height = heights[i] if i!= len(heights) else 0
            while stack and height <= heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] -1 if stack else i
                res = max(res, h*w)
                print("res equals {}".format(res))
                print("h equals {}".format(h))
                print("w equals {}".format(w))
                print("stack equals {}".format(stack))
            stack.append(i)
        return res
largestRectangleArea([2,3,1,2,3,1])

res equals 3
h equals 3
w equals 1
stack equals [0]
res equals 4
h equals 2
w equals 2
stack equals []
res equals 4
h equals 3
w equals 1
stack equals [2, 3]
res equals 4
h equals 2
w equals 2
stack equals [2]
res equals 5
h equals 1
w equals 5
stack equals []
res equals 6
h equals 1
w equals 6
stack equals []





6

85. Maximal Rectangle

class Solution(object):
    def maximalRectangle(self, matrix):
    	# O(m^2)
        if not matrix or not matrix[0]:
            return 0
        n = len(matrix[0])
        # init heights array
        height = [0] * (n + 1)
        ans = 0
        # calculate each row
        for row in matrix:
            for i in range(n):
                # count next level '1'
                height[i] = height[i] + 1 if row[i] == '1' else 0

            stack = []

            for i in range(n + 1):
                while stack and height[i] <= height[stack[-1]]:
                    h = height[stack.pop()]
                    # if not stack means left boundary is zero then width is i else is the stack[-1] index
                    w = i - 1 - stack[-1] if stack else i
                    ans = max(ans, h * w)
                stack.append(i)
        return ans