旧题记录：

https://blog.csdn.net/chamao_/article/details/143775934?fromshare=blogdetail&sharetype=blogdetail&sharerId=143775934&sharerefer=PC&sharesource=chamao_&sharefrom=from_link

C++解法：

class StackOfPlates {
private:
    vector<vector<int>> stacks;
    int cap;
public:
    StackOfPlates(int cap) {
        this -> cap = cap;
    }
    
    void push(int val) {
        if (cap == 0) return;
        if (stacks.empty() || stacks.back().size() == cap) {
            stacks.push_back(vector<int>());
        }
        stacks.back().push_back(val);
    }
    
    int pop() {
        if (stacks.empty()) return -1;
        int val = stacks.back().back();
        stacks.back().pop_back();
        if (stacks.back().empty()) {
            stacks.pop_back();
        }
        return val;
    }
    
    int popAt(int index) {
        if (index < 0 || index >= stacks.size() || stacks[index].empty()) return -1;
        int val = stacks[index].back();
        stacks[index].pop_back();
        if (stacks[index].empty()) {
            stacks.erase(stacks.begin() + index);
        }
        return val;
    }
};

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates* obj = new StackOfPlates(cap);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAt(index);
 */

今天来了解vector的常用接口：

一、vector 是什么（一句话）

std::vector<T>

👉 动态连续数组

• 内存连续

• 支持随机访问 O(1)

• 尾部插入 / 删除高效

---

二、容量 & 状态相关（非常常用）

1️⃣ size()

v.size();

• 返回当前元素个数

• 类型是 size_t（无符号）

⚠️ 注意：

for (int i = 0; i < v.size(); ++i) // 潜在警告

更安全：

for (size_t i = 0; i < v.size(); ++i)

---

2️⃣ empty()

v.empty();

• 是否为空

• 比 size() == 0 更语义化

---

3️⃣ capacity()

v.capacity();

• 当前分配的最大容量

• ≥ size()

---

4️⃣ reserve(n)

v.reserve(100);

• 提前分配内存

• 避免频繁扩容（性能优化）

⚠️ 不改变 size！

---

5️⃣ resize(n)

v.resize(5);

• 改变 size

• 扩大 → 用默认值填充

• 缩小 → 多余元素被销毁

---

三、元素访问（刷题必会）

6️⃣ operator[]

v[i];

• O(1)

• 不做越界检查（最快）

---

7️⃣ at()

v.at(i);

• 越界会抛 std::out_of_range

• 调试时更安全

---

8️⃣ front() / back()

v.front(); // 第一个 v.back(); // 最后一个

⚠️ vector 不能为空！

---

9️⃣ data()

int* p = v.data();

• 返回底层连续内存指针

• 可与 C API / memcpy 交互

---

四、修改元素（核心操作）

🔟 push_back()

v.push_back(x);

• 尾插

• 均摊 O(1)

---

1️⃣1️⃣ emplace_back()

v.emplace_back(1, 2);

• 原地构造

• 避免临时对象（性能更优）

---

1️⃣2️⃣ pop_back()

v.pop_back();

• 删除最后一个

• 不返回值

---

1️⃣3️⃣ insert()

v.insert(v.begin() + i, x);

• 在任意位置插入

• O(n)（元素搬移）

---

1️⃣4️⃣ erase()

v.erase(v.begin() + i);

或区间：

v.erase(v.begin(), v.begin() + 3);

• 删除元素

• 后续元素前移

---

1️⃣5️⃣ clear()

v.clear();

• 清空所有元素

• capacity 不变

---

五、迭代器相关（工程 & STL 算法）

1️⃣6️⃣ begin() / end()

for (auto it = v.begin(); it != v.end(); ++it) { ... }

---

1️⃣7️⃣ rbegin() / rend()

for (auto it = v.rbegin(); it != v.rend(); ++it) { ... }

---

1️⃣8️⃣ cbegin() / cend()

for (auto it = v.cbegin(); it != v.cend(); ++it) { ... }

• 返回 const_iterator

---

六、赋值 & 构造相关

1️⃣9️⃣ 构造函数

vector<int> v1; // 空 vector<int> v2(5); // 5 个 0 vector<int> v3(5, 3); // 5 个 3 vector<int> v4 = {1,2,3}; // 初始化列表 vector<int> v5(v4); // 拷贝构造

---

2️⃣0️⃣ assign()

v.assign(5, 10); // 5 个 10

---

2️⃣1️⃣ swap()

v1.swap(v2);

• O(1)

• 常用于 快速清空内存

vector<int>().swap(v);