Monotonic Stack - Identify Pattern

Stack: 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) / FILO (First In Last Out) 형식의 자료 구조.

가장 최근에 더해진 항목이 가장 먼저 제거되는 구조이며, pop(), push(item), peek(), Empty() 등의 functions이 있다.

The functions associated with stack are:

• empty(): returns whether the stack is empty - Time complexity: O(1)
• size(): returns the size of the stack - Time complexity: O(1)
• top()/ peek(): returns a reference to the topmost element of the stack - Time complexity: O(1)
• push(a): inserts the element 'a' at the top of the stack - Time complexity: O(1)
• pop(): deletes the topmost element of the stack - Time complexity: O(1)

https://www.geeksforgeeks.org/stack-in-python/

Stack in Python - GeeksforGeeks

 

Array대신 Stack을 쓰는게 더 좋은 경우가 있다. Stack에서는 데이터를 추가하거나 삭제하는 연산을 O(1) time complexity안에 할 수 있으며, array처럼 원소들을 하나씩 옆으로 밀어줄 필요가 없다. 또한 Stack은 Linked List로 구현할 수 있다.

• Example of Stack: 웹 브라우저 방문기록(뒤로가기), 실행취소(Undo), 역순 문자열 만들기, 수식의 괄호 검사(올바른 괄호문자열 Valid Parenthesis String 판단), 후위 표기법 계산 등 

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

[자료구조] 스택(Stack)이란 - Heee's Development Blog

 

Monotonic stack is a stack whose elements are monotonically increasing or decreasing. It contains all qualities that a typical stack has and its elements are all monotonic decreasing or increasing.

Below are the features of a monotonic stack:

• It is a range of queries in an array situation
• The minima/maxima elements
• When an element is popped from the monotonic stack, it will never be utilised again.

The monotonic stack problem is mainly the previous/next smalleer/larger problem. It maintains monotonicity while popping elements when a new item is pushed into the stack.

Keep on pushing the elements in the stack until it is on an element that is smaller than the stack's top and when it reaches such a number, it keeps on popping the stack till the point where it is either empty or its top is smaller than its current element. Therefore all the elements in the stack are in increasing order from bottom to top. 

https://itnext.io/monotonic-stack-identify-pattern-3da2d491a61e

Monotonic Stack — Identify Pattern

Example: nums = [2, 3, 7, 11, 5, 17, 19] -> output: [2, 3, 5, 17, 19]

def monotonicStack(nums):
	n = len(nums)
    stack = []
    
    for i in range(n):
    	while len(stack)>0 and stack[-1] >= nums[i]: #[-1] means the last element in a sequence.
        stack.pop()
        
        stack.append(nums[i])
    return stack

if __name__ == '__main__':
	result = monotonicStack(nums)
    print(result)

Monotonic Stack Related Problem & Solution

1. Next Greater Element: Get the next greater element for every array element.

• Input: nums = [2, 7, 3, 5, 4, 6, 8]
• Output: [7, 8, 5, 6, 6, 8, -1]

def getNextGreaterElements(nums):
	n = len(nums)
    stack = []
    result = [-1] * n
    
    for i in range(n): #7개 원소가 있음
    	while len(stack)>0 and nums[stack[-1]] < nums[i]: 
        #stack[-1]란 list(stack)의 마지막 원소 값. 
        	result[stack[-1]] = nums[i]
            stack.pop()
        stack.append(i)
    return result

2. Next Greater Element I

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. 

• Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
• Output: [-1,3,-1]

class Solution(object):
	def nextGreaterElement(self, nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    stack = []
    d = {}
    for i in range(len(nums2)):
    	d[nums2[i]] = -1
    for i in range(len(nums2)):
    	while len(stack) > 0 and nums2[i]>stack[-1]:
        	item = stack.pop()
            d[item] = nums2[i]
            
        stack.append(nums2[i])
        
    for i in range(len(nums1)):
    	nums1[i] = d[nums1[i]]
    return nums1

3. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0], return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 this number. 

• Input: nums = [1,2,1]
• Output: [2,-1,2]

class Solution(object):
	def nextGreaterElements(self, nums):
    """
    :type nums:List[int]
    :rtype List[int]
    """
    n=len(nums)
    stack = []
    result = [-1]*n
    for i in range(2*n-1):
    	index = i%n
        while stack and stack[-1][1] < nums[index]:
        	resIndex, _ = stack.pop()
            result[resIndex] = nums[index]
        stack.append([index, nums[index]])
    return result