[LeetCode] 155. Min Stack(最小栈)

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

设计一个栈,支持 push, pop, top 以及取最小元素(全部操作要求在常数时间内完成)

  • push(x) -- Push element x onto stack.

    push(x) -- 将元素 x 入栈

  • pop() -- Removes the element on top of the stack.

    pop() -- 将栈顶元素出栈

  • top() -- Get the top element

    top() -- 获得栈顶元素

  • getMin() -- Retrieve the minimum element in the stack.

    getMin() -- 获取栈内的最小元素

Example

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

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints

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

    方法 pop, topgetMin 总是会在栈非空时调用

Hint

  1. Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)

    考虑栈内的每个节点带上最小元素信息

Solution

数据结构设计题没啥好讲的,根据提示做即可,代码如下:

import kotlin.math.min

class MinStack() {

    /** initialize your data structure here. */

    /**
     * 定义 `pair.first` 为当前元素,`pair.second` 为栈内的最小元素
     */
    private val stack = arrayListOf<Pair<Int, Int>>()

    fun push(x: Int) {
        if (stack.isEmpty()) {
            // 栈为空时,直接加入
            stack.add(Pair(x, x))
            return
        }
        // 栈非空,把当前最小值拿出来,与要插入的元素比较决定是否更新最小值
        val currentMin = stack.last().second
        stack.add(Pair(x, min(x, currentMin)))
    }

    fun pop() {
        stack.removeAt(stack.lastIndex)
    }

    fun top(): Int {
        return stack.last().first
    }

    fun getMin(): Int {
        return stack.last().second
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */
上一篇:209. 长度最小的子数组


下一篇:java - 冒泡加递归 求数组最小值