找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2609|回复: 6
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【MinStack】【栈】-【刷题第一弹】

[复制链接]

23

主题

16

精华

1207

积分

顶级会员

Rank: 6Rank: 6

积分
1207

推广达人宣传达人突出贡献

发表于 11-10-2014 10:34 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-6-2014 10:44 PM 编辑

快速通道:
https://oj.leetcode.com/problems/min-stack/

一直 爆空间,本来幻想着,数据弱一点,能用一个stack<int>水过,还是没成功,总体空间复杂度没有变,发一个贴,欢迎讨论
题目:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.




建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================







思路:

LC上能AC的 ,请参考cpcs思路:http://www.meetqun.com/forum.php?mod=viewthread&tid=1948&ctid=2
我的不能AC:
记录当前最小值,与实际值的差值,注意到当遇到比当前值更小的值时,差值一定为负。那么我们只要用一个变量记录最小值
当出栈时,如果sval.top()<0时,那么更新最小值再出栈。
记得要在栈为空的地方,把cur_max清零

代码
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <list>
  7. #include <string>
  8. #include <map>
  9. //#include <unordered_map>
  10. #include <set>
  11. #include <bitset>
  12. #include <string>
  13. #include <cstring>
  14. #include <cmath>
  15. #include <climits>
  16. #include <cstdlib>
  17. #include <cassert>
  18. using namespace std;
  19. class MinStack {
  20. private:
  21.     stack<long long> sval;
  22.     long long cur_min ;
  23. public:
  24.     void push(int x) {
  25.         if (sval.empty()) {
  26.             sval.push(0);
  27.             cur_min = x;
  28.             return;
  29.         }else
  30.         {
  31.         //        cout<<"push:"<<x<< ";"<<"pre_min"<<cur_min<<";deta:"<<x-cur_min<<endl;
  32.             sval.push(x - cur_min);
  33.             if (x< cur_min) cur_min=x;
  34.            // cout<<"cur_min:"<< cur_min<<endl;
  35.         }
  36.     }

  37.     void pop() {
  38.         if (sval.empty()) throw runtime_error("empty stack");
  39.         if (sval.top()<0) cur_min = cur_min-sval.top();
  40.         sval.pop();
  41.         if (sval.empty()) cur_min = 0;
  42.     }

  43.     int top()throw() {
  44.         if(sval.empty()) throw runtime_error("empty stack");
  45.         if (sval.top()<0) return cur_min;
  46.         return sval.top() + cur_min;
  47.     }

  48.     int getMin() throw() {
  49.         if (sval.empty()) throw runtime_error("empty stack");
  50.         return cur_min;
  51.     }
  52. };
  53. int main()
  54. {   MinStack s;
  55.         s.push(INT_MAX-1);
  56.         s.push(INT_MAX-1);
  57.         s.push(INT_MAX);
  58.         cout<<s.top()<<endl;
  59.         s.pop();
  60.         cout<<s.getMin()<<endl;
  61.         s.pop();
  62.         cout<<s.getMin()<<endl;
  63.         s.pop();
  64.         s.push(INT_MAX);
  65.         cout<<s.top()<<endl;
  66.         cout<<s.getMin()<<endl;
  67.         s.push(INT_MIN);
  68.         cout<<s.top()<<endl;
  69.         cout<<s.getMin()<<endl;
  70.         s.pop();
  71.         cout<<s.getMin()<<endl;

  72.         return 0 ;
  73. }
复制代码


复杂度:
空间复杂度 其实也是O(2*N),尽管只用了一个栈,因为要避免越界,不得不用long long类型

本帖被以下淘专辑推荐:

11

主题

6

精华

600

积分

版主

Rank: 7Rank: 7Rank: 7

积分
600
发表于 11-11-2014 01:03 AM | 显示全部楼层
在min stack上下点功夫,就可以让第二个stack的数量远小于第一个stack,就不会爆memory了……

  1. class MinStack {
  2.     private Stack<Integer> s = new Stack<Integer>();
  3.     private Stack<Integer> m = new Stack<Integer>();
  4.    
  5.     public void push(int x) {
  6.         s.push(x);
  7.         if (m.isEmpty() || m.peek() >= x) m.push(x);
  8.     }

  9.     public void pop() {
  10.         int k = s.pop();
  11.         if (m.peek() == k) m.pop();
  12.     }

  13.     public int top() {
  14.         return s.peek();
  15.     }

  16.     public int getMin() {
  17.         return m.peek();
  18.     }
  19. }
复制代码
回复 支持 1 反对 0

使用道具 举报

发表于 11-11-2014 12:05 AM | 显示全部楼层
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表