What is the best way to solve Min Stack?

The optimized O(1) approach using Stack patterns is generally preferred.

상위 150개 인터뷰쉬움

최소 스택

'최소 스택' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

푸시, 팝, 상단 및 일정한 시간에 최소 요소 검색을 지원하는 스택을 설계합니다.

MinStack 클래스를 구현합니다.

- MinStack()은 스택 개체를 초기화합니다.

- push(val: int)는 val 요소를 스택에 푸시합니다.

- pop()는 스택 맨 위에 있는 요소를 제거합니다.

- top() -> int는 스택의 최상위 요소를 가져옵니다.

- getMin() -> int은 스택의 최소 요소를 검색합니다.

각 기능에 대해 O(1) 시간 복잡도를 갖는 솔루션을 구현해야 합니다.

제약

•-2^31 <= val <= 2^31 - 1
•Methods pop, top, and getMin are always called on non-empty stacks
•At most 3 * 10^4 calls will be made to push, pop, top, and getMin

예

Example 1

Input

["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
[[], [-2], [0], [-3], [], [], [], []]

Output

[None, None, None, None, -3, None, 0, -2]

Explanation

MinStack created. Push -2, 0, -3. getMin() returns -3. Pop removes -3. top() returns 0. getMin() returns -2.

Need a Hint?

세트나 힙과 같은 스택별 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

스택 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

class MinStackOpt:
    def __init__(self):
        self.stack = []
        self.minStack = []
    def push(self, val: int) -> None:
        self.stack.append(val)
        val = min(val, self.minStack[-1] if self.minStack else val)
        self.minStack.append(val)
    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()
    def top(self) -> int:
        return self.stack[-1]
    def getMin(self) -> int:
        return self.minStack[-1]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

class MinStackBrute:
    def __init__(self):
        self.stack = []
    def push(self, val: int) -> None:
        self.stack.append(val)
    def pop(self) -> None:
        self.stack.pop()
    def top(self) -> int:
        return self.stack[-1]
    def getMin(self) -> int:
        return min(self.stack)