⭐️ 题目日期：

腾讯 - 2024/8/19

🌳 题目描述：

使用数组实现栈，支持常数时间复杂度的 push，pop，max 操作；

栈：按照后进先出的原理运作，在栈顶进行元素的加入与弹出

示例1：

🕵🏽 面试评估：

这道题考察候选人对栈后进先出特性的理解，且能否使用一个辅助数组来存储最大值来保证 max 操作能在常数级时间完成。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

针对这道题，我们采用两个数组来存储，stack 数组来存储实际的元素，MaxStack 数组来存储当前栈中的最大值

以案例一为例，解析如下。

当执行 push(x) ,首先更新 top 栈顶指针的值，随后将 x 加入数组中，同时判断当前的数是否大于等于 MaxStack 数组中最顶端的数，或者是当前的数是否为第一个数，如果是，便将其压入 MaxStack 数组中，确保 MaxStack 数组总是包含当前 stack 数组中的最大值。

当执行 pop()，将栈顶指针的值 -1即可

当执行 top()，返回当前数组栈顶指针所指的数值

当执行 max()，返回 MaxStack 数组栈顶指针所指的数值

💻代码：

Java

public class MyStack {
    private int[] stack;       // 存储栈中的元素
    private int[] maxStack;    // 存储栈中的最大值
    private int top;           // 表示栈顶指针
    private int capacity;      // 栈的当前容量

    public MyStack() {
        this.capacity = 10;   // 设置初始容量为 10
        this.stack = new int[capacity];
        this.maxStack = new int[capacity];
        this.top = -1;        // 栈顶指针初始化为 -1
    }

    public void push(int x) {
        // 判断是否需要进行扩容操作
        if (top + 1 == capacity) {
            expandCapacity(); // 扩容操作
        }
        top++;
        stack[top] = x;

        if (top == 0 || x >= maxStack[top - 1]) {
            maxStack[top] = x;
        } else {
            maxStack[top] = maxStack[top - 1];
        }
    }

    public void pop() {
        if (top >= 0) {
            top--;
        } else {
            throw new IllegalStateException("栈为空!");
        }
    }

    public int top() {
        if (top >= 0) {
            return stack[top];
        }
    
        return -1;
    }

    public int max() {
        if (top >= 0) {
            return maxStack[top];
        }
        
        return -1;
    }

    private void expandCapacity() {
        capacity *= 2; // 扩容为原来的两倍
        stack = Arrays.copyOf(stack, capacity);
        maxStack = Arrays.copyOf(maxStack, capacity);
    }
}

Python

class MyStack:
    def __init__(self):
        self.capacity = 10  # 初始容量
        self.stack = [0] * self.capacity  # 存储栈中的元素
        self.max_stack = [0] * self.capacity  # 存储栈中的最大值
        self.top = -1  # 栈顶指针初始化为 -1

    def push(self, x):
        # 判断是否需要扩容
        if self.top + 1 == self.capacity:
            self.expend_capacity()
        self.top += 1
        self.stack[self.top] = x

        if self.top == 0 or x >= self.max_stack[self.top - 1]:
            self.max_stack[self.top] = x
        else:
            self.max_stack[self.top] = self.max_stack[self.top - 1]
    
    def pop(self):
        if self.top >= 0:
            self.top -= 1
        else:
            raise Exception("栈为空！")

    def get_top(self):
        if self.top >= 0:
            return self.stack[self.top]
        return -1

    def max(self):
        if self.top >= 0:
            return self.max_stack[self.top]
        return -1

    def expend_capacity(self):
        self.capacity *= 2
        self.stack.extend([0] * (self.capacity // 2))
        self.max_stack.extend([0] * (self.capacity // 2))

🚵🏻复杂度分析：

时间复杂度：O(1)，pop 和 max 时间复杂度均为 O(1), push 操作如果容量满需要进行扩容，平均时间复杂度为 O(1)。

空间复杂度：O(n)，使用两个数组来存储数据，其中 n 为栈中元素的个数。