查看: 6204| 回复: 28
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
我觉得网上答案已经可以了,为什么我看到有几个版本的答案复杂的恐怖,又是double linkedlist又是treemap神马的?
public class MaxStack<T> {
        LinkedList<T> stack;
    PriorityQueue<T> maxHeap;

    public MaxStack() {
        stack = new LinkedList<T>();
        maxHeap = new PriorityQueue<T>(10, Collections.reverseOrder());  
    }

    public void push(T num) {
        stack.addLast(num);
        maxHeap.offer(num);
    }

    public T pop() {
        T num = stack.removeLast();
        maxHeap.remove(num);
        return num;
    }

    public T peek() {
        return stack.peekLast();
    }

    public T peekMax() {
        return maxHeap.peek();
    }

    public T popMax() {     
        T num = maxHeap.poll();
        stack.remove(num);
        return num;
    }

    public static void main(String[] args) {
        MaxStack<Integer> stack = new MaxStack<Integer>();
        int[] arr = {3, 1, 2, 4, 6, 5};
        for (Integer n: arr) {
            stack.push(n);
        }
        System.out.println(stack.popMax());  // 6
        System.out.println(stack.popMax());  // 5
        System.out.println(stack.popMax());  // 4
        System.out.println(stack.pop());     // 2
        System.out.println(stack.popMax());  // 3
    }

评分

参与人数 1大米 +5 收起 理由
ivanyang + 5 感谢分享!

查看全部评分


上一篇:每次看到Accepted Solutions Runtime Distribution就难过
下一篇:找人在millbrae附近周末刷题
推荐
heroic 2017-10-16 07:37:59 | 只看该作者
全局:
没有所有操作的O(1)解。否则你把乱序的n个元素的数组push进去 不停的运行popmax() n次得到一个有序数组。这样可以实现O(n)的排序 这是不可能的
回复

使用道具 举报

推荐
wtcupup 2017-10-16 06:11:52 | 只看该作者
全局:
Heap push 不是O(1)吧
回复

使用道具 举报

推荐
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. }
复制代码
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 06:19:38 | 只看该作者
全局:
wtcupup 发表于 2017-10-16 06:11
Heap push 不是O(1)吧

嗯, 你是指“stack.addLast(num);”
linkedlist 的addLast操作不是O(1)?
回复

使用道具 举报

🔗
wtcupup 2017-10-16 06:20:54 | 只看该作者
全局:
我一辈子赖美帝 发表于 2017-10-16 06:19
嗯, 你是指“stack.addLast(num);”
linkedlist 的addLast操作不是O(1)?

MaxHeap offer不是O(1)
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 06:22:59 | 只看该作者
全局:
wtcupup 发表于 2017-10-16 06:20
MaxHeap offer不是O(1)

嗷,真的咧,多谢。没注意这一点,看来代码全部要重写了
回复

使用道具 举报

🔗
xujr 2017-10-16 06:51:03 | 只看该作者
全局:
maxHeap.remove(num)是不是也不是O(1)?
回复

使用道具 举报

🔗
ivanyang 2017-10-16 06:53:44 | 只看该作者
全局:
LZ有网上答案的link吗?能分享一下吗?非常感谢。
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 06:54:26 | 只看该作者
全局:
贴一个我的版本,popMax 我不确定到底是不是O1,因为value Stack里的值没有变化。
class MaxStackII {
    private Stack<Integer> valueStack;
    private Stack<Integer> maxStack;
   
    public void push(int value){
        valueStack.push(value);
        if (maxStack.isEmpty() || value > maxStack.peek()){
            maxStack.push(value);
        }
    }
   
    public void pop(){
        int value = valueStack.peek();
        valueStack.pop();
        if (value == maxStack.peek()){
            maxStack.pop();
        }
    }
   
    public void popMax(){
            maxStack.pop();//but value stack's element not updated? how to modify them by O1?
           
    }
   
   
    public int max(){
        return maxStack.peek();
    }
回复

使用道具 举报

🔗
yesterdaysea 2017-10-16 06:55:13 | 只看该作者
全局:
你的popmax()是O(n). 1) java pq remove() 是O(n). 2) linkedList remove() 也是O(n).
回复

使用道具 举报

🔗
 楼主| 我一辈子赖美帝 2017-10-16 06:55:25 | 只看该作者
全局:
ivanyang 发表于 2017-10-16 06:53
LZ有网上答案的link吗?能分享一下吗?非常感谢。

之前那个错误版本就是在网上找的,作者还说是O1,幸亏今天我抽筋double check发现是错的
回复

使用道具 举报

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

本版积分规则

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