LeetCode Day 58 Monotonic Stack (1/3)

Dynamic programming is finished, coming to the last piece of content: the monotonic stack, which is just three days of content in total.

1. Fundamental knowledges of monotonic stack

1.1 When to use monotonic stack?

Usually a one-dimensional array, to find the location of the first element to the right or left of any element larger or smaller than itself, at this point we have to think that we can use a monotonic stack. The time complexity is O(n).

The essence of the monotonic stack is space for time, because in the process of traversal of the need to use a stack to record the first right than the current element of the element, the advantage is that the entire array only needs to be traversed once.

More bluntly, is to use a stack to record the elements we have traversed, because we traverse the array, we do not know what elements have been traversed before, so traversing an element can not be found is not traversed before a smaller, so we need to use a container (here with a monotonic stack) to record our traversal of the elements.

1.2 Three main judgement conditions for using a monotonic stack.

• The case where the currently traversed element T[i] is less than the top stack element T[st.top()].
• The case where the currently traversed element T[i] is equal to the top element T[st.top()].
• The case where the currently traversed element T[i] is greater than the top of the stack element T[st.top()].

2. Question 1

739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

The Brute Force is still the first thing that comes to mind, a two level for loop that scours out the number of days to wait at least. The time complexity is O(n^2).

This is a question that applies a monotonic stack and is analysed to cover the following three cases:

• Case 1: The current traversed element T[i] is less than the top element T[st.top()] of the stack
• Case 2: The case where the currently traversed element T[i] is equal to the top stack element T[st.top()].
• Case 3: the current traversal of the element T[i] is greater than the top of the stack element T[st.top()].

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0]*len(temperatures)
        stack = [0]
        for i in range(1,len(temperatures)):
 
            if temperatures[i]<=temperatures[stack[-1]]:
                stack.append(i)
 
            else:
                while len(stack) != 0 and temperatures[i]>temperatures[stack[-1]]:
                    answer[stack[-1]]=i-stack[-1]
                    stack.pop()
                stack.append(i)
 
        return answer

3. Question 2

496. Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

To analyse the following three cases.

• Case 1: the current traversal of the element T[i] is less than the top of the stack element T[st.top()] case
  • At this time to meet the incremental stack (the order of the stack head to the bottom of the stack), so directly into the stack.
• Case 2: the current traversal of the element T[i] is equal to the top of the stack element T[st.top()] case
  • If equal, still directly into the stack, because we require the first element on the right than their own, rather than greater than or equal to!
• Case 3: the current traversal of the element T[i] is greater than the top of the stack element T[st.top()] case
  • At this point if the stack into the stack will not satisfy the incremental stack, this is also to find the right side of the first element larger than their own time.

Determine whether the top element of the stack has appeared in nums1, (note that the elements in the stack are elements of nums2), if it has appeared, start recording results.

Record the results of this piece of logic there is a little bit around, to be clear, at this time, the top of the stack element in the nums2 array on the right side of the first larger element is nums2[i] (that is, the current traversal of the element).

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [-1]*len(nums1)
        stack = [0]
        for i in range(1,len(nums2)):
            if nums2[i]<=nums2[stack[-1]]:
                stack.append(i)
            else:
                while len(stack)!=0 and nums2[i]>nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        result[index]=nums2[i]
                    stack.pop()                 
                stack.append(i)
        return result