Stack

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Stackも比較的easyな印象。Arrays & Hashing, Two Pointers よりはちょっと難しいかも。

15. Valid Parentheses

Problem

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

Every open bracket is closed by the same type of close bracket.

Open brackets are closed in the correct order.

Every close bracket has a corresponding open bracket of the same type.

Return true if s is a valid string, and false otherwise.

Example 1:

Input: s = "[]"

Output: true

Example 2:

Input: s = "([{}])"

Output: true

Example 3:

Input: s = "[(])"

Output: false

Explanation: The brackets are not closed in the correct order.

Constraints:

1 <= s.length <= 1000

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        close_open_map = {')': '(', ']': '[', '}': '{'}
        stack = []
        i = 0

        while i < len(s):
            # s[i]が「), }, ]」のどれかだったら
            # stackの一番上の値を取り出してマッチするか調べる
            if s[i] in close_open_map:
                # そもそもstackに値がないケースもあるので確認
                if not stack:
                    return False
                
                top = stack.pop()
                if top != close_open_map[s[i]]:
                    return False
            else:
                stack.append(s[i])
            i += 1
        
        # 最後stackが空になってたらOK
        return not stack

16. Min Stack

Problem

Design a stack class that supports the push, pop, top, and getMin operations.

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

Each function should run in O(1) time.

Example 1:

Input: ["MinStack", "push", 1, "push", 2, "push", 0, "getMin", "pop", "top", "getMin"]

Output: [null,null,null,null,0,null,2,1]

Explanation:

MinStack minStack = new MinStack();

minStack.push(1);

minStack.push(2);

minStack.push(0);

minStack.getMin(); // return 0

minStack.pop();

minStack.top(); // return 2

minStack.getMin(); // return 1

Constraints:

-2^31 <= val <= 2^31 - 1.

pop, top and getMin will always be called on non-empty stacks.

Solution

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        # 最小値を上に積む
        # valの方が小さければそれを積む
        # 現時点での最小値の方が小さければそれを再度上に積む
        # そもそもmin_stackにまだ値がない可能性もあるので注意
        min_val = val
        if self.min_stack and self.min_stack[-1] < val:
            min_val = self.min_stack[-1]
        self.min_stack.append(min_val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

17. Evaluate Reverse Polish Notation

Problem

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.

The operators include '+', '-', '*', and '/'.

Assume that division between integers always truncates toward zero.

Example 1:

Input: tokens = ["1","2","+","3","*","4","-"]

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

1 <= tokens.length <= 1000.

tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

Solution

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operations = {'+', '-', '*', '/'}
        stack = []

        for token in tokens:
            if token in operations:
                first, second = stack.pop(), stack.pop()
                if token == '+':
                    stack.append(second + first)
                elif token == '-':
                    stack.append(second - first)
                elif token == '*':
                    stack.append(second * first)
                else:
                    stack.append(int(second / first))
            else:
                stack.append(int(token))
        
        # 最後にstackに残ってる値が答え
        return stack[-1]

18. Generate Parentheses

Problem

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.

The operators include '+', '-', '*', and '/'.

Assume that division between integers always truncates toward zero.

Example 1:

Input: tokens = ["1","2","+","3","*","4","-"]

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

1 <= tokens.length <= 1000.

tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

Solution

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        stack = []
        
        def dfs(open_n: int, close_n: int) -> None:
            if close_n == n:
                # stackをそのまま渡しちゃうとその後の処理で変化し続けてしまう

                res.append(''.join(stack.copy()))
                return
            
            if open_n < n:
                stack.append('(')
                dfs(open_n + 1, close_n)
                stack.pop()
            
            if close_n < open_n:
                stack.append(')')
                dfs(open_n, close_n + 1)
                stack.pop()
        
        dfs(0, 0)
        return res

19. Daily Temperatures

Problem

You are given an array of integers temperatures where temperatures[i] represents the daily temperatures on the ith day.

Return an array result where result[i] is the number of days after the ith day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the ith day, set result[i] to 0 instead.

Example 1:

Input: temperatures = [30,38,30,36,35,40,28]

Output: [1,4,1,2,1,0,0]

Example 2:

Input: temperatures = [22,21,20]

Output: [0,0,0]

Constraints:

1 <= temperatures.length <= 1000.

1 <= temperatures[i] <= 100

Solution

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [] # index of temperatures
        res = [0] * len(temperatures)
        
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                top_i = stack.pop()
                # indexの差(何日後に暖かい日が来たか)を設定
                res[top_i] = i - top_i

            stack.append(i)
        
        return res

20. Car Fleet

Problem

There are n cars traveling to the same destination on a one-lane highway.

You are given two arrays of integers position and speed, both of length n.

position[i] is the position of the ith car (in miles)

speed[i] is the speed of the ith car (in miles per hour)

The destination is at position target miles.

A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.

A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.

If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.

Return the number of different car fleets that will arrive at the destination.

Example 1:

Input: target = 10, position = [1,4], speed = [3,2]

Output: 1

Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.

Example 2:

Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]

Output: 3

Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.

Constraints:

n == position.length == speed.length.

1 <= n <= 1000

0 < target <= 1000

0 < speed[i] <= 100

0 <= position[i] < target

All the values of position are unique.

Solution

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        p_s_zip = [(p, s) for p, s in zip(position, speed)]

        # positionでソートする
        # O(N log N)
        p_s_zip.sort()
        stack = [] # arrival_time

        # 後ろから順に走査する
        for p, s in p_s_zip[::-1]:
            rest_distance = target - p
            # arrival time to reach target
            # targetへの到着時刻
            arrival_time = rest_distance / s

            if not stack or (stack and stack[-1] < arrival_time):
                # 同時に到着したら一つのフリートなので、
                # 先頭の車よりも遅く到着予定の場合だけstackに追加する
                stack.append(arrival_time)
        
        return len(stack)

21. Largest Rectangle In Histogram

Problem

You are given an array of integers heights where heights[i] represents the height of a bar. The width of each bar is 1.

Return the area of the largest rectangle that can be formed among the bars.

Note: This chart is known as a histogram.

Example 1:

Input: heights = [7,1,7,2,2,4]

Output: 8

Example 2:

Input: heights = [1,3,7]

Output: 7

Constraints:

1 <= heights.length <= 1000.

0 <= heights[i] <= 1000

Solution

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [] # (height, index)
        max_area = 0

        for i, h in enumerate(heights):
            # 最後にpopした値のindexを保持したい
            top_i = i
            while stack and h < stack[-1][0]:
                tmp_h, tmp_i = stack.pop()
                top_i = tmp_i
                width = i - top_i
                area = width * tmp_h
                max_area = max(max_area, area)
            # 最後にpopした値のindexを設定しておく
            stack.append((h, top_i))
        
        # 最後にstackに残ってる値について面積を計算する
        while stack:
            top_h, top_i = stack.pop()
            width = len(heights) - top_i
            area = width * top_h
            max_area = max(max_area, area)
        
        return max_area