stack<int> 底层容器连续性

今日力扣是关于单调栈的，刚开始我使用stack实现，最后题目要求返回vector，因为c++把stack视为容器而不是迭代器，所以使用pointer来计算stack的起始终止位置，如以下代码。

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<int> stk;
        int n = nums.size();
        for(int i=0;i<n;i++){
            while(!stk.empty() && nums[i] < stk.top() && stk.size() + n - i - 1>= k)
                stk.pop();
            stk.push(nums[i]);
        }
        int *begin = &stk.top() + 1 - stk.size();
        return vector<int>(begin, begin + k);
    }
};

但以上代码过不了最后几个用例，报heap-overflow，判断可能是stack的内存连续性问题。因为stack默认使用deque(即双端数组)作为底层容器，实际上一个逻辑数组在内存中分块存储的。以下是llama-70b的回答。

That's correct. `std::deque` does not guarantee contiguous memory allocation. It's a double-ended queue that typically uses a sequence of fixed-size arrays (called "blocks" or "chunks") to store its elements. Each block has a fixed capacity, and when the deque grows or shrinks, new blocks are allocated or deallocated as needed.

The elements in a `std::deque` are not stored in a single contiguous block of memory. Instead, the deque maintains a sequence of pointers to these blocks, which allows it to efficiently insert or remove elements at any position.

This design provides several benefits, such as:

1. Efficient insertion and deletion at any position, with an average time complexity of O(1).
2. Good cache locality for iterating over the elements.
3. Ability to handle large datasets without running out of contiguous memory.

However, this design also means that `std::deque` does not provide a contiguous block of memory, which can be a limitation in certain situations, such as:

1. When you need to pass a pointer to a contiguous array to a C-style API or a function that expects a contiguous array.
2. When you need to use pointer arithmetic or indexing into the array.

In contrast, `std::vector` does guarantee contiguous memory allocation, which is why it's often preferred when contiguous memory is required.

In the case of `std::stack`, when you use the default underlying container (`std::deque`), you don't have a guarantee of contiguous memory. But when you specify `std::vector` as the underlying container, you do get contiguous memory, which is why the original code worked when using `stack<int, vector<int>>`.

解决方案： stack<int> → stack<int, vector<int>>