Leetcode 热题100-155 最小栈
1. 题目描述
2. 解题思路
方法一:创建一个辅助栈min_stk
用以存储当前元素相对应的栈中最小元素值;
方式二:类似于方法一,使用pair<int,int>
同时存储当前元素与其对应的栈中最小元素值。
3. 代码实现(方法二)
class MinStack {
// 存储与每个元素以及相对应的栈中的最小值
stack<pair<int,int>> stk;
public:
MinStack() {
// 初始化堆栈对象
stk.push({INT_MAX, INT_MAX});
}
void push(int val) { stk.push({val, min(val, stk.top().second)}); }
void pop() { stk.pop(); }
int top() { return stk.top().first; }
int getMin() { return stk.top().second; }
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
4. c++知识点
std::pair
是一个简单的容器类模板,用于存储两个相关联的对象。它的主要用途是将两个值组合在一起,形成一个单独的实体。以下是 std::pair
的主要用法:
用法
- 创建和初始化:
- 可以直接创建并初始化一个
std::pair
对象。 - 可以使用
std::make_pair
函数来创建一个std::pair
对象。
- 可以直接创建并初始化一个
std::pair<int, std::string> p1(1, "example");
auto p2 = std::make_pair(2, "example2");
- 访问元素与修改元素:
- 通过成员变量
first
和second
来访问std::pair
的两个元素。 - 可以直接修改
first
和second
的值。
- 通过成员变量
int num = p1.first; // 访问第一个元素
std::string str = p1.second; // 访问第二个元素
p1.first = 10; // 修改第一个元素
p1.second = "ten"; // 修改第二个元素
- 比较:
std::pair
支持按字典顺序进行比较(先比较first
元素,如果first
相等,再比较second
元素)。- 提供了
==
,!=
,<
,<=
,>
,>=
等比较操作符。
if (p1 < p2) {
// 按字典顺序比较
}
- 使用场景:
- 返回多个值:函数返回一对相关的值时,可以使用
std::pair
。 - 容器中的元素:在
std::map
和std::unordered_map
等关联容器中,键值对存储为std::pair
。 - 暂时组合两个值:在算法中临时组合两个相关的值。
- 返回多个值:函数返回一对相关的值时,可以使用