leetcode1475. 商品折扣后的最终价格 【单调栈】

简单题

第一次错误做法

class Solution {
public:vector<int> finalPrices(vector<int>& prices) {int n = prices.size();stack<int> st;unordered_map<int, int> mp;int i = 0;while(i != prices.size()) {int t = prices[i];if (st.empty() || t > st.top()) {st.push(t);i++;}else if (t <= st.top()) {int x = st.top();st.pop();mp[x] = x - t;}}while (!st.empty()) {int x = st.top();mp[x] = x;st.pop();}vector<int> ans;for(int i = 0; i < n; i++){ans.push_back(mp[prices[i]]);}return ans;}
};

运行结果：

错误分析：入栈的是元素，如果之后出现相等的元素，则会覆盖哈希表中的值。

正确思路：

修改入栈元素为下标之后：

class Solution {
public:vector<int> finalPrices(vector<int>& prices) {int n = prices.size();stack<int> st;vector<int> num(n);int i = 0;while(i != prices.size()) {int t = prices[i];if (st.empty() || t > prices[st.top()]) {st.push(i);i++;}else if (t <= prices[st.top()]) {int x = st.top();st.pop();num[x] = prices[x] - t;}}// 如果栈中还有元素(数组中没有比它小的值，没得优惠，就只能付原价啦)while (!st.empty()) {int x = st.top();num[x] = prices[x];st.pop();}return num;}
};

for遍历数组元素写法：

class Solution {
public:vector<int> finalPrices(vector<int>& prices) {int n = prices.size();vector<int> ans(n);stack<int> st;for (int i = 0; i < n; i++) {int t = prices[i];while (!st.empty() && t <= prices[st.top()]) {int x = st.top();ans[x] = prices[x] - t;st.pop();}while (st.empty() || t > prices[st.top()]) {st.push(i);}}while (!st.empty()) {int x = st.top();ans[x] = prices[x];st.pop();}return ans;}
};

 为什么运行时间变长了？