2024/09/30 Leetcode Daily Problem

1381. Design a Stack With Increment Operation
難度: 中等偏易

題意

設計一個支援元素遞增操作的堆疊。支援以下操作:
CustomStack(int maxSize)：用 maxSize 初始化這個物件，maxSize 是堆疊的最大元素數量。
void push(int x)：如果堆疊未達最大容量，將元素 x 加入堆疊頂部。
int pop()：彈出並回傳堆疊頂部的元素，若堆疊為空則回傳 -1。
void increment(int k, int val)：將堆疊底部的前 k 個元素遞增 val。如果堆疊中元素少於 k 個，則遞增堆疊中的所有元素。

思路

這次就不直接用STL std::stack了~
直接用陣列和一個索引代表下一個要插入的位置。void increment(int k, int val)直接操作陣列。

實作

class CustomStack
{
private:
    int size = 0;
    int idx = 0;
    vector<int> stack;

public:
    CustomStack(int maxSize)
    {
        this->stack = vector<int>(maxSize);
        this->size = maxSize;
        this->idx = 0;
    }

    void push(int x)
    {
        if (idx < size)
        {
            stack[idx] = x;
            idx++;
        }
    }

    int pop()
    {
        if (idx > 0)
        {
            int res = stack[idx - 1];
            idx--;
            return res;
        }
        return -1;
    }

    void increment(int k, int val)
    {
        for (int i = 0; i < min(k, idx); i++)
            stack[i] += val;
    }
};

結果

Accepted
34/34 cases passed (32 ms)
Your runtime beats 28.06 % of cpp submissions
Your memory usage beats 66.84 % of cpp submissions (25.9 MB)

總結