高级农民
- 积分
- 2725
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-6-18
- 最后登录
- 1970-1-1
|
本帖最后由 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或以上编译):- #include <cstddef>
- #include <cstddef>
- #include <cstdint>
- #include <cstdlib>
- #include <functional>
- #include <iostream>
- #include <map>
- #include <type_traits>
- // 链表节点
- template <typename T>
- class ListNode {
- public:
- explicit ListNode(const T value)
- : value_(value),
- trie_prev_(nullptr),
- trie_next_(nullptr),
- stak_prev_(nullptr),
- stak_next_(nullptr) {}
- inline T value() const {
- return value_;
- }
- inline void erase() {
- if (stak_prev_ != nullptr) {
- stak_prev_->stak_next_ = stak_next_;
- }
- if (stak_next_ != nullptr) {
- stak_next_->stak_prev_ = stak_prev_;
- }
- if (trie_prev_ != nullptr) {
- trie_prev_->trie_next_ = trie_next_;
- }
- if (trie_next_ != nullptr) {
- trie_next_->trie_prev_ = trie_prev_;
- }
- }
- inline void pushStack(ListNode *next) {
- ListNode *next_next = stak_next_;
- stak_next_ = next;
- next->stak_next_ = next_next;
- next->stak_prev_ = this;
- if (next_next != nullptr) {
- next_next->stak_prev_ = next;
- }
- }
- inline void pushTrie(ListNode *next) {
- ListNode *next_next = trie_next_;
- trie_next_ = next;
- next->trie_next_ = next_next;
- next->trie_prev_ = this;
- if (next_next != nullptr) {
- next_next->trie_prev_ = next;
- }
- }
- inline ListNode* peekStack() const {
- // assert stak_next_ != nullptr
- return stak_next_;
- }
- inline ListNode* popStack() {
- // assert stak_next_ != nullptr
- ListNode *node = stak_next_;
- node->erase();
- return node;
- }
- inline ListNode* peekTrie() const {
- // assert trie_next_ != nullptr
- return trie_next_;
- }
- inline ListNode* popTrie() {
- // assert trie_next_ != nullptr
- ListNode *node = trie_next_;
- node->erase();
- return node;
- }
- inline bool isEmptyTrie() const {
- return trie_next_ == nullptr;
- }
- private:
- const T value_;
- ListNode *trie_prev_;
- ListNode *trie_next_;
- ListNode *stak_prev_;
- ListNode *stak_next_;
- template <typename, std::size_t> friend class TrieNode;
- template <typename> friend class MaxStack;
- };
- // Trie的中间节点
- template <typename T, std::size_t degree>
- class TrieNode {
- public:
- inline void push(const T value, ListNode<T> *node) {
- const std::uint8_t byte = static_cast<std::uint8_t>(value >> kShift);
- // Worst-case O(log(256)) to locate children_[byte]
- children_[byte].push(value, node);
- }
- inline ListNode<T>* peekMax() {
- // Worst-case O(256)
- while (!children_.empty()) {
- auto it = children_.begin();
- ListNode<T> *node = it->second.peekMax();
- if (node != nullptr) {
- return node;
- }
- children_.erase(it);
- }
- return nullptr;
- }
- inline ListNode<T>* popMax() {
- // Worst-case O(256), amortized O(1)
- while (!children_.empty()) {
- auto it = children_.begin();
- ListNode<T> *node = it->second.popMax();
- if (node != nullptr) {
- return node;
- }
- children_.erase(it);
- }
- return nullptr;
- }
- private:
- static constexpr std::size_t kShift = degree * 8;
- using ChildNode = TrieNode<T, degree - 1>;
- std::map<std::uint8_t, ChildNode, std::greater<std::uint8_t>> children_;
- };
- // Trie的叶子节点
- template <typename T>
- class TrieNode<T, 0> {
- public:
- inline void push(const T value, ListNode<T> *node) {
- const std::uint8_t byte = static_cast<std::uint8_t>(value);
- ListNode<T> *&head = leafs_[byte];
- if (head == nullptr) {
- head = new ListNode<T>(0);
- }
- head->pushTrie(node);
- }
- inline ListNode<T>* peekMax() {
- // Worst-case O(256)
- while (!leafs_.empty()) {
- auto it = leafs_.begin();
- if (!it->second->isEmptyTrie()) {
- return it->second->peekTrie();
- }
- delete it->second;
- leafs_.erase(it);
- }
- return nullptr;
- }
- inline ListNode<T>* popMax() {
- // Worst-case O(256), amortized O(1)
- while (!leafs_.empty()) {
- auto it = leafs_.begin();
- if (!it->second->isEmptyTrie()) {
- return it->second->popTrie();
- }
- delete it->second;
- leafs_.erase(it);
- }
- return nullptr;
- }
- private:
- std::map<std::uint8_t, ListNode<T>*, std::greater<std::uint8_t>> leafs_;
- };
- // Max stack的实现
- template <typename T>
- class MaxStack {
- public:
- MaxStack()
- : size_(0),
- stack_(new ListNode<T>(0)) {}
- ~MaxStack() {
- delete stack_;
- }
- void push(const T value) {
- ListNode<T> *node = new ListNode<T>(value);
- stack_->pushStack(node);
- trie_.push(encodeSigned<T>(value), node);
- ++size_;
- }
- T peek() const {
- // assert size_ != 0;
- return stack_->peekStack()->value();
- }
- T pop() {
- // assert size_ != 0;
- ListNode<T> *node = stack_->popStack();
- const T value = node->value();
- delete node;
- --size_;
- return value;
- }
- T peekMax() {
- // assert size_ != 0;
- return trie_.peekMax()->value();
- }
- T popMax() {
- // assert size_ != 0;
- ListNode<T> *node = trie_.popMax();
- const T value = node->value();
- delete node;
- --size_;
- return value;
- }
- std::size_t size() const {
- return size_;
- }
- void empty() const {
- return size_ == 0;
- }
- private:
- static constexpr std::size_t kNumBytes = sizeof(T);
- static constexpr T kTopBit = static_cast<T>(1) << (kNumBytes * 8 - 1);
- // 对于有符号整数,我们需要偏移一下以将其当做无符号整数处理
- template <typename U>
- inline T encodeSigned(
- const T value,
- typename std::enable_if<std::is_signed<U>::value>::type * = 0) const {
- // Flip the top bit.
- return value ^ kTopBit;
- }
- template <typename U>
- inline T encodeSigned(
- const T value,
- typename std::enable_if<!std::is_signed<U>::value>::type * = 0) const {
- return value;
- }
- std::size_t size_;
- TrieNode<T, kNumBytes-1> trie_;
- ListNode<T> *stack_;
- };
- int main(int argc, char *argv[]) {
- MaxStack<int> stack;
- stack.push(-200000000);
- stack.push(0);
- stack.push(200000000);
- stack.push(100000000);
- stack.push(-100000000);
- std::cout << stack.peek() << "\n";
- std::cout << stack.peekMax() << "\n";
- std::cout << stack.popMax() << "\n";
- std::cout << stack.peek() << "\n";
- std::cout << stack.peekMax() << "\n";
- std::cout << stack.popMax() << "\n";
- std::cout << stack.pop() << "\n";
- std::cout << stack.peekMax() << "\n";
- std::cout << stack.pop() << "\n";
- std::cout << stack.peek() << "\n";
- std::cout << stack.popMax() << "\n";
- std::cout << stack.size() << "\n";
- return 0;
- }
复制代码 |
|