123
返回列表 发新帖
跳转到指定楼层
上一主题 下一主题
收起左侧

L家一道题max Stack 要求全部O(1) 看看我的解答对吗

🔗
ivanyang 2017-10-16 07:41:05 | 只看该作者
全局:
本帖最后由 ivanyang 于 2017-10-16 07:49 编辑
  1. class MaxStack {
  2.     list<int> stack;
  3.     list<list<list<int>::iterator>> maxStack;
  4.    
  5.     void push(int val) {
  6.         stack.push_back(val);
  7.         if (maxStack.size() == 0) {
  8.             list<list<int>::iterator>> to_push;
  9.             to_push.push_back(--stack.end());
  10.             maxStack.push_back(to_push);
  11.         } else {
  12.             int nowMax = *maxStack.back().back();
  13.             if (nowMax < val) {
  14.                 list<list<int>::iterator>> to_push;
  15.                 to_push.push_back(--stack.end());
  16.                 maxStack.push_back(to_push);
  17.             } else if (nowMax == val) {
  18.                 maxStack.back().push_back(--stack.end());
  19.             }
  20.         }
  21.     }

  22.     void pop() {
  23.         int val = stack.back();
  24.         stack.pop_back();
  25.         int maxNow = *maxStack.back().back();
  26.         if (val == maxNow) {
  27.             maxStack.back().pop_back();
  28.             if (maxStack.back().size() == 0) {
  29.                 maxStack.pop_back();
  30.             }
  31.         }
  32.     }
  33.    
  34.     int peek() {
  35.         return stack.back();
  36.     }

  37.     int peekMax() {
  38.         return *maxStack.back().back();
  39.     }

  40.     void popMax() {
  41.         auto maxNow = maxStack.back().back();
复制代码
C++ 不保证能编译,不保证正确。这个是错误的,把stack改成单向链表的话然后把maxNOW之后的断掉可以做成每次popMax把max顶上的元素pop掉,但想只pop max element 是不可能的。
回复

使用道具 举报

🔗
CiciR 2017-10-16 08:58:20 | 只看该作者
全局:
用两stack不行吗?就跟做minstack一样
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 09:41:57 | 只看该作者
全局:
CiciR 发表于 2017-10-16 08:58
用两stack不行吗?就跟做minstack一样

目前我的方法就是2个stack,但popMax怎么O1?
回复

使用道具 举报

🔗
DetectiveConan 2017-10-20 03:06:57 | 只看该作者
全局:
heroic 发表于 2017-10-16 07:37
没有所有操作的O(1)解。否则你把乱序的n个元素的数组push进去 不停的运行popmax() n次得到一个有序数组。这 ...

赞,顶一个。用归谬法证明。这个证明有一个大前提是sort是comparison-based的,upper limit is nlogn。如果是给定范围的话,那么用bucket sort/radix sort,可以做到O(n)。这道题目应该是针对任意n个数字,所以O(nlogn)是极限了。由此,必然有一个操作是bottleneck。
回复

使用道具 举报

🔗
moonyellow 2017-10-20 18:07:28 | 只看该作者
全局:
DetectiveConan 发表于 2017-10-20 03:06
赞,顶一个。用归谬法证明。这个证明有一个大前提是sort是comparison-based的,upper limit is nlogn。如 ...

同意,应该并不存在全O(1)的解。
回复

使用道具 举报

🔗
ld_xixi 2017-11-7 14:26:57 | 只看该作者
全局:
我一辈子赖美帝 发表于 2017-10-16 06:54
贴一个我的版本,popMax 我不确定到底是不是O1,因为value Stack里的值没有变化。
class MaxStackII {
   ...

这个答案有问题, 如果先压大的数字, 小的数字永远不会被压倒maxStack里, pop的操作就没法更新maxstack
回复

使用道具 举报

🔗
magicsets 2017-11-8 07:19:18 | 只看该作者
全局:
本帖最后由 magicsets 于 2017-11-8 10:33 编辑

这道题目是可以有全O(1)的解法的——准确来说是worst case O(1000)左右,而且内存占用量的常数因子很大,所以没有任何实用价值——但毕竟在算法层面上是与input的长度n(stack的大小)无关了。

Comparison-based的方法确实没有办法做到O(1),所以我们要用(identity) hash-based的方法,简单来说就是Trie,也就是把一个整数拆成多个byte(int型是4个byte),然后逐层建树。

那么处理每一层的代价至多就是O(256),4层就是O(1000)左右。

参考代码如下(需要用C++11或以上编译):
  1. #include <cstddef>
  2. #include <cstddef>
  3. #include <cstdint>
  4. #include <cstdlib>
  5. #include <functional>
  6. #include <iostream>
  7. #include <map>
  8. #include <type_traits>

  9. // 链表节点
  10. template <typename T>
  11. class ListNode {
  12. public:
  13.   explicit ListNode(const T value)
  14.       : value_(value),
  15.         trie_prev_(nullptr),
  16.         trie_next_(nullptr),
  17.         stak_prev_(nullptr),
  18.         stak_next_(nullptr) {}

  19.   inline T value() const {
  20.     return value_;
  21.   }

  22.   inline void erase() {
  23.     if (stak_prev_ != nullptr) {
  24.       stak_prev_->stak_next_ = stak_next_;
  25.     }
  26.     if (stak_next_ != nullptr) {
  27.       stak_next_->stak_prev_ = stak_prev_;
  28.     }
  29.     if (trie_prev_ != nullptr) {
  30.       trie_prev_->trie_next_ = trie_next_;
  31.     }
  32.     if (trie_next_ != nullptr) {
  33.       trie_next_->trie_prev_ = trie_prev_;
  34.     }
  35.   }

  36.   inline void pushStack(ListNode *next) {
  37.     ListNode *next_next = stak_next_;
  38.     stak_next_ = next;
  39.     next->stak_next_ = next_next;
  40.     next->stak_prev_ = this;
  41.     if (next_next != nullptr) {
  42.       next_next->stak_prev_ = next;
  43.     }
  44.   }

  45.   inline void pushTrie(ListNode *next) {
  46.     ListNode *next_next = trie_next_;
  47.     trie_next_ = next;
  48.     next->trie_next_ = next_next;
  49.     next->trie_prev_ = this;
  50.     if (next_next != nullptr) {
  51.       next_next->trie_prev_ = next;
  52.     }
  53.   }

  54.   inline ListNode* peekStack() const {
  55.     // assert stak_next_ != nullptr
  56.     return stak_next_;
  57.   }

  58.   inline ListNode* popStack() {
  59.     // assert stak_next_ != nullptr
  60.     ListNode *node = stak_next_;
  61.     node->erase();
  62.     return node;
  63.   }

  64.   inline ListNode* peekTrie() const {
  65.     // assert trie_next_ != nullptr
  66.     return trie_next_;
  67.   }

  68.   inline ListNode* popTrie() {
  69.     // assert trie_next_ != nullptr
  70.     ListNode *node = trie_next_;
  71.     node->erase();
  72.     return node;
  73.   }

  74.   inline bool isEmptyTrie() const {
  75.     return trie_next_ == nullptr;
  76.   }

  77. private:
  78.   const T value_;
  79.   ListNode *trie_prev_;
  80.   ListNode *trie_next_;
  81.   ListNode *stak_prev_;
  82.   ListNode *stak_next_;

  83.   template <typename, std::size_t> friend class TrieNode;
  84.   template <typename> friend class MaxStack;
  85. };

  86. // Trie的中间节点
  87. template <typename T, std::size_t degree>
  88. class TrieNode {
  89. public:
  90.   inline void push(const T value, ListNode<T> *node) {
  91.     const std::uint8_t byte = static_cast<std::uint8_t>(value >> kShift);
  92.     // Worst-case O(log(256)) to locate children_[byte]
  93.     children_[byte].push(value, node);
  94.   }

  95.   inline ListNode<T>* peekMax() {
  96.     // Worst-case O(256)
  97.     while (!children_.empty()) {
  98.       auto it = children_.begin();
  99.       ListNode<T> *node = it->second.peekMax();
  100.       if (node != nullptr) {
  101.         return node;
  102.       }
  103.       children_.erase(it);
  104.     }
  105.     return nullptr;
  106.   }

  107.   inline ListNode<T>* popMax() {
  108.     // Worst-case O(256), amortized O(1)
  109.     while (!children_.empty()) {
  110.       auto it = children_.begin();
  111.       ListNode<T> *node = it->second.popMax();
  112.       if (node != nullptr) {
  113.         return node;
  114.       }
  115.       children_.erase(it);
  116.     }
  117.     return nullptr;
  118.   }

  119. private:
  120.   static constexpr std::size_t kShift = degree * 8;
  121.   using ChildNode = TrieNode<T, degree - 1>;
  122.   std::map<std::uint8_t, ChildNode, std::greater<std::uint8_t>> children_;
  123. };

  124. // Trie的叶子节点
  125. template <typename T>
  126. class TrieNode<T, 0> {
  127. public:
  128.   inline void push(const T value, ListNode<T> *node) {
  129.     const std::uint8_t byte = static_cast<std::uint8_t>(value);
  130.     ListNode<T> *&head = leafs_[byte];
  131.     if (head == nullptr) {
  132.       head = new ListNode<T>(0);
  133.     }
  134.     head->pushTrie(node);
  135.   }

  136.   inline ListNode<T>* peekMax() {
  137.     // Worst-case O(256)
  138.     while (!leafs_.empty()) {
  139.       auto it = leafs_.begin();
  140.       if (!it->second->isEmptyTrie()) {
  141.         return it->second->peekTrie();
  142.       }
  143.       delete it->second;
  144.       leafs_.erase(it);
  145.     }
  146.     return nullptr;
  147.   }

  148.   inline ListNode<T>* popMax() {
  149.     // Worst-case O(256), amortized O(1)
  150.     while (!leafs_.empty()) {
  151.       auto it = leafs_.begin();
  152.       if (!it->second->isEmptyTrie()) {
  153.         return it->second->popTrie();
  154.       }
  155.       delete it->second;
  156.       leafs_.erase(it);
  157.     }
  158.     return nullptr;
  159.   }

  160. private:
  161.   std::map<std::uint8_t, ListNode<T>*, std::greater<std::uint8_t>> leafs_;
  162. };

  163. // Max stack的实现
  164. template <typename T>
  165. class MaxStack {
  166. public:
  167.   MaxStack()
  168.       : size_(0),
  169.         stack_(new ListNode<T>(0)) {}

  170.   ~MaxStack() {
  171.     delete stack_;
  172.   }

  173.   void push(const T value) {
  174.     ListNode<T> *node = new ListNode<T>(value);
  175.     stack_->pushStack(node);
  176.     trie_.push(encodeSigned<T>(value), node);
  177.     ++size_;
  178.   }

  179.   T peek() const {
  180.     // assert size_ != 0;
  181.     return stack_->peekStack()->value();
  182.   }

  183.   T pop() {
  184.     // assert size_ != 0;
  185.     ListNode<T> *node = stack_->popStack();
  186.     const T value = node->value();
  187.     delete node;
  188.     --size_;
  189.     return value;
  190.   }

  191.   T peekMax() {
  192.     // assert size_ != 0;
  193.     return trie_.peekMax()->value();
  194.   }

  195.   T popMax() {
  196.     // assert size_ != 0;
  197.     ListNode<T> *node = trie_.popMax();
  198.     const T value = node->value();
  199.     delete node;
  200.     --size_;
  201.     return value;
  202.   }

  203.   std::size_t size() const {
  204.     return size_;
  205.   }

  206.   void empty() const {
  207.     return size_ == 0;
  208.   }

  209. private:
  210.   static constexpr std::size_t kNumBytes = sizeof(T);
  211.   static constexpr T kTopBit = static_cast<T>(1) << (kNumBytes * 8 - 1);

  212.   // 对于有符号整数,我们需要偏移一下以将其当做无符号整数处理
  213.   template <typename U>
  214.   inline T encodeSigned(
  215.       const T value,
  216.       typename std::enable_if<std::is_signed<U>::value>::type * = 0) const {
  217.     // Flip the top bit.
  218.     return value ^ kTopBit;
  219.   }

  220.   template <typename U>
  221.   inline T encodeSigned(
  222.       const T value,
  223.       typename std::enable_if<!std::is_signed<U>::value>::type * = 0) const {
  224.     return value;
  225.   }

  226.   std::size_t size_;
  227.   TrieNode<T, kNumBytes-1> trie_;
  228.   ListNode<T> *stack_;
  229. };

  230. int main(int argc, char *argv[]) {
  231.   MaxStack<int> stack;
  232.   stack.push(-200000000);
  233.   stack.push(0);
  234.   stack.push(200000000);
  235.   stack.push(100000000);
  236.   stack.push(-100000000);

  237.   std::cout << stack.peek() << "\n";
  238.   std::cout << stack.peekMax() << "\n";
  239.   std::cout << stack.popMax() << "\n";
  240.   std::cout << stack.peek() << "\n";
  241.   std::cout << stack.peekMax() << "\n";
  242.   std::cout << stack.popMax() << "\n";
  243.   std::cout << stack.pop() << "\n";
  244.   std::cout << stack.peekMax() << "\n";
  245.   std::cout << stack.pop() << "\n";
  246.   std::cout << stack.peek() << "\n";
  247.   std::cout << stack.popMax() << "\n";
  248.   std::cout << stack.size() << "\n";

  249.   return 0;
  250. }
复制代码
回复

使用道具 举报

🔗
Urumic 2017-12-18 02:17:46 | 只看该作者
全局:
请问这道题的要求是常数时间复杂度吗?看大家好像都在纠结这个。能否将以下这道题的具体要求哈。谢谢啦!
回复

使用道具 举报

🔗
Urumic 2017-12-18 04:08:41 | 只看该作者
全局:
  1. class MaxStack {
  2.     private Stack<Integer> stack;
  3.     private Stack<Integer> maxStack;

  4.     /** initialize your data structure here. */
  5.     public MaxStack() {
  6.         stack = new Stack<>();
  7.         maxStack = new Stack<>();
  8.     }
  9.    
  10.     public void push(int x) {
  11.         if (maxStack.isEmpty() || x >= maxStack.peek()) {
  12.             maxStack.push(x);
  13.         }
  14.         
  15.         stack.push(x);
  16.     }
  17.    
  18.     public int pop() {
  19.         if (!maxStack.isEmpty() && maxStack.peek() == stack.peek()) {
  20.             maxStack.pop();
  21.         }
  22.         
  23.         int ret = stack.pop();
  24.         return ret;
  25.     }
  26.    
  27.     public int top() {
  28.         return stack.peek();
  29.     }
  30.    
  31.     public int peekMax() {
  32.         return maxStack.peek();
  33.     }
  34.    
  35.     public int popMax() {
  36.         int curMax = maxStack.peek();
  37.         Stack<Integer> tmp = new Stack<>();
  38.         while (curMax != stack.peek()) {
  39.             tmp.push(stack.pop());
  40.         }
  41.         
  42.         maxStack.pop();
  43.         stack.pop();
  44.         
  45.         while (!tmp.isEmpty()) {
  46.             this.push(tmp.pop());
  47.         }
  48.         
  49.         return curMax;
  50.     }
  51. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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