细语呢喃

技术改变生活

0%

leetcode 数据结构

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括

  • 20. Valid Parentheses
  • 146 LRU Cache
  • 150 Evaluate Reverse Polish Notation
  • 155 Min Stack
  • 187 Repeated DNA Sequences
  • 208 Implement Trie (Prefix Tree)
  • 211 Add and Search Word - Data structure design
  • 218 The Skyline Problem
  • 232 Implement Queue using Stacks
  • 239 Sliding Window Maximum
  • 341 Flatten Nested List Iterator
  • 352 Data Stream as Disjoint Intervals
  • 432 All O'one Data Structure
    1. 下一个更大元素 II

20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

题目地址：leetcode Valid Parentheses

题目大意 给定三种括号组成的字符串，让你判断是否合法

思路

用栈判断即可。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	bool isValid(string s) {
		stack<char> q;
		for (char c : s) {
			if (c == '[' || c == '{' || c == '(')
				q.push(c);
			else {
				if (q.empty()) return false;
				char top = q.top();
				q.pop();
				if (c == ')' && top != '(' || c == '}' && top != '{' || c == ']' && top != '[')
					return false;
			}
		}
		return q.empty();
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        q = []
        for c in s:
            if c in ['(','{','[']:
                q.append(c)
            else:
                if not q: return False
                top = q.pop()
                if c == ')' and top != '(' or c == '}' and top != '{' or c == ']' and top != '[':
                    return False
        return not q

 

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

传送门

题意：设计一个数据结构，要求实现LRU（Least Recently Used 即最近最不常使用）功能

  • get(key)： 获取Key对应的值，如果不存在返回-1
  • set(key, value) ： 设置key的值为value，超过容量，那么应先删除最近最不常使用的元素，再插入

思路：

LRU是在OS课上有讲过。当我们访问过一个元素，设置一个元素的时候，都应该标记一下刚使用过。

我是用字典+链表实现的。要点如下

  • 构造函数中创建一个list q和一个字典dic
  • get时候，如果元素存在，将q中对应的key删除，并将其插入队尾
  • set时候，如果元素不存在且容量过大，删除队首元素，将新的插入队尾和字典。如果元素存在，只需要设置字典，和将q中对应的调到队尾即可。（先删除后插入）

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct DoubleListNode {
	DoubleListNode *pre;
	DoubleListNode *next;
    int key;
	int val;
	DoubleListNode(int k, int v) : key(k), val(v), pre(nullptr), next(nullptr) {}
};

class DoubleLinkList {
	DoubleListNode *head;
	DoubleListNode *tail;
public:
	DoubleLinkList(){
		head = new DoubleListNode(-1, -1);
		tail = new DoubleListNode(-1, -1);
		head->next = tail;
		tail->pre = head;
	}

	DoubleListNode* removeHead() {
		return remove(head->next);
	}

	DoubleListNode* remove(DoubleListNode *t) {
		if (t == head || t == tail) return nullptr;
		DoubleListNode *pre = t->pre;
		DoubleListNode *next = t->next;
		pre->next = next;
		next->pre = pre;
		return t;
	}

	void insertTail(DoubleListNode *t) {
		DoubleListNode *pre = tail->pre;
		t->pre = pre;
		t->next = tail;
		pre->next = t;
		tail->pre = t;
	}
};


class LRUCache {
	int capacity;
	unordered_map<int, DoubleListNode*> hashmap;
	DoubleLinkList list;
public:
	LRUCache(int capacity) : capacity(capacity) {}

	int get(int key) {
		if (hashmap.find(key) == hashmap.end())
			return -1;
		DoubleListNode *t = hashmap[key];
		list.remove(t);
		list.insertTail(t);
		return t->val;
	}

	void put(int key, int value) {
		if (hashmap.find(key) != hashmap.end()) {
			DoubleListNode *t = hashmap[key];
			list.remove(t);
			list.insertTail(t);
			t->val = value;
		}
		else {
			if (hashmap.size() >= capacity) {
				DoubleListNode *t = list.removeHead();
                hashmap.erase(t->key);
                delete t;
			}
			DoubleListNode *t = new DoubleListNode(key, value);
			hashmap[key] = t;
			list.insertTail(t);
		}
	}
};

 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Node(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.pre = None

class DoubleLinkList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def pop(self, node=None):
        if not node:
            node = self.tail
        pre, next = node.pre, node.next
        if pre and next:
            pre.next = next
            next.pre = pre
        
        if node == self.tail:
            self.tail = self.tail.pre
        if node == self.head:
            self.head = self.head.next
        return node

    def insert_head(self, node):
        if not self.head:
            self.head = self.tail = node
        else:
            node.next = self.head
            node.pre = self.tail
            self.head.pre = node
            self.tail.next = node
            self.head = node

class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.map = {}
        self.linklist = DoubleLinkList()

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.map.get(key)
        if not node: return -1
        self.linklist.pop(node)
        self.linklist.insert_head(node)
        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.map:
            node = self.linklist.pop(self.map[key])
            node.value = value
        else:
            if len(self.map) == self.capacity:
                node = self.linklist.pop()
                del self.map[node.key]
            node = Node(key, value)
            self.map[key] = node
        self.linklist.insert_head(node)


Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class LinkedListNode {
    int key;
    int value;
    LinkedListNode pre;
    LinkedListNode next;

    LinkedListNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DoubleLinkedList {
    LinkedListNode head = null;
    LinkedListNode tail = null;

    LinkedListNode removeTail() {
        return remove(tail);
    }

    LinkedListNode remove(final LinkedListNode node) {
        LinkedListNode pre = node.pre, next = node.next;
        if (pre != null)
            pre.next = next;
        if (next != null)
            next.pre = pre;
        if (node == head) head = head.next;
        if (node == tail) tail = tail.pre;
        return node;
    }

    void insertHead(LinkedListNode node) {
        if (head == null)
            head = tail = node;
        else {
            node.next = head;
            node.pre = tail;
            head.pre = node;
            tail.next = node;
            head = node;
        }
    }
}

public class LRUCache {
    int capacity;
    DoubleLinkedList list;
    HashMap<Integer, LinkedListNode> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.list = new DoubleLinkedList();
    }

    public int get(int key) {
        LinkedListNode node = map.get(key);
        if (node == null) return -1;
        list.insertHead(list.remove(node));
        return node.value;
    }

    public void put(int key, int value) {
        LinkedListNode node = map.get(key);
        if (node != null) {
            node.value = value;
            list.insertHead(list.remove(node));
        } else {
            if(map.size() == capacity){
                node = list.removeTail();
                map.remove(node.key);
            }
            node = new LinkedListNode(key,value);
            map.put(key,node);
            list.insertHead(node);
        }
    }
}


 

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

1
2
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

传送门

题意：给定一个字符串数组（后缀表达式）求其计算结果

思路：遇到四则运算符时候，从栈中取出两个元素进行计算。然后入栈。

我巧妙的运用了异常处理，代码更简洁、更优雅。

还有就是Python负数除法需要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # @param tokens, a list of string
    # @return an integer
    def evalRPN(self, tokens):
        stack  = [] 
        for i in tokens:
            try:
                temp = int(i)
                stack.append(temp)
            except Exception, e:         
                b,a=stack[-1],stack[-2]
                stack.pop()
                stack.pop()
                if i == '+':    a = a+b
                elif i=='-':    a = a-b
                elif i=='*':    a = a*b
                elif i=='/':    a = int(a*1.0/b)
                stack.append(a)
        return stack[-1]

 

155. Min Stack

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.

传送门

题意：设计一个数据结构，要求实现如下功能

  • push(x) -- 把x入栈
  • pop() -- 删除栈顶
  • top() -- 获取top元素
  • getMin() -- 返回栈中最小元素

思路：双栈，用另一个栈来维护到当前位置最小的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        if not self.min or x <= self.min[-1]: self.min.append(x)

    def pop(self):
        """
        :rtype: void
        """
        x = self.stack.pop()
        if x == self.min[-1]: self.min.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: int
        """
        return self.min[-1]

 

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MinStack {
    std::stack<int> s;
    std::stack<int> min_s;
public:
    /** initialize your data structure here. */
    MinStack() {}
    
    void push(int x) {
        s.push(x);
        if (min_s.empty() || min_s.top() >= x) {
            min_s.push(x);
        }
    }
    
    void pop() {
        int x = s.top();
        s.pop();
        if (x == min_s.top()) {
            min_s.pop();
        }
    }
    
    int top() {
        return s.top();
    }
    
    int min() {
        return min_s.top();
    }
};

187. Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

1
2
3
4
5
6
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].


传送门

题意：给定一个DNA字符串，返回不只出现过一次的10个字符长的子串

思路：枚举所有10字符的子串，直接用哈希表即可

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        dic ,ans, n=set(),set(),len(s)
        for i in xrange(n-9):
            cur = s[i:i+10]
            if cur in dic:
                ans.add(cur)
            else: dic.add(cur)
        return list(ans)

 

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note: You may assume that all inputs are consist of lowercase letters a-z.

传送门

题意：要求实现前缀树。

思路：直接写呗。。。

我是用结点上的end判断是否有以这个字母作为结束的单词。因为相同单词路径唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class TrieNode {
public:
	static const int c_size = 26;
	bool end;
	TrieNode *child[26];
	// Initialize your data structure here.
	TrieNode() {
		end = false;
		for (int i = 0; i < c_size; i++) child[i] = NULL;
	}
};

class Trie {
public:
	Trie() {
		root = new TrieNode();
	}

	inline int index(const char &c){
		return c - 'a';
	}

	// Inserts a word into the trie.
	void insert(string word) {
		TrieNode *p = root;
		for (int i = 0; i < word.length(); i++){
			int id = index(word[i]);
			if (!p->child[id]){
				TrieNode *t = new TrieNode();
				p->child[id] = t;
			}
			p = p->child[id];
		}
		p->end = true;
	}

	// Returns if the word is in the trie.
	bool search(string word) {
		TrieNode *p = match_word(word);
		return p && p->end;
	}

	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
		return match_word(prefix);
	}

	~Trie() {
		deleteNode(root);
	}

	void deleteNode(TrieNode *root){
		if (!root) return;
		for (int i = 0; i < TrieNode::c_size; i++){
			deleteNode(root->child[i]);
		}
		delete root;
	}

private:
	TrieNode* root;

	TrieNode*  match_word(const string &word){
		TrieNode *p = root;
		for (int i = 0; i < word.length(); i++){
			int id = index(word[i]);
			if (!p->child[id])	return NULL;
			p = p->child[id];
		}
		return p;
	}
};

 

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

1
2
3
void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters a-z.

传送门

题意：和上一题一样，实现个数据结构，有插入和查找功能。查找的时候'.'可以代替任意字符。

思路：就是search的时候需要注意.的情况需要遍历当前层所有的点

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class TrieNode {
public:
	static const int c_size = 26;
	bool end;
	TrieNode *child[26];
	// Initialize your data structure here.
	TrieNode() {
		end = false;
		for (int i = 0; i < c_size; i++) child[i] = NULL;
	}
};

class WordDictionary {
public:
	WordDictionary() {
		root = new TrieNode();
	}

	inline int index(const char &c){
		return c - 'a';
	}

	// Adds a word into the data structure.
	void addWord(string word) {
		TrieNode *p = root;
		for (int i = 0; i < word.length(); i++){
			int id = index(word[i]);
			if (!p->child[id]){
				TrieNode *t = new TrieNode();
				p->child[id] = t;
			}
			p = p->child[id];
		}
		p->end = true;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		return match_word(root,0,word);
	}

	~WordDictionary() {
		deleteNode(root);
	}

	void deleteNode(TrieNode *root){
		if (!root) return;
		for (int i = 0; i < TrieNode::c_size; i++){
			deleteNode(root->child[i]);
		}
		delete root;
	}

private:
	TrieNode* root;
	bool match_word(TrieNode *p ,int k,const string &word){
		if (!p || k > word.length()) return false;
		if (k == word.length() && p->end) return true;
		for (; k < word.length(); k++){
			if (word[k] == '.') {
				for (int j = 0; j < TrieNode::c_size; j++){
					if (match_word(p->child[j], k + 1, word))
						return true;
				}
				return false;
			}
			else{
				int id = index(word[k]);
				if (!p->child[id])	return false;
				p = p->child[id];
			}
		}
		return p->end;
	}
};

 

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example, Given words = ["oath","pea","eat","rain"] and board =

1
2
3
4
5
6
7
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note: You may assume that all inputs are consist of lowercase letters a-z.

传送门

题意：给定一个矩阵和一些单词，求能在矩阵中找到的所有单词。（通过上下、左右相邻拼接，但是每个字符只能使用一次）

思路：和79题的DFS方法差不多，就是要求效率更高。所以可以使用前缀树！看看当前路径上前缀树是否有，若没有，则直接剪枝了。

79 Word Search的题解： https://www.hrwhisper.me/?p=523

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class TrieNode {
public:
	static const int c_size = 26;
	bool end;
	TrieNode *child[26];
	// Initialize your data structure here.
	TrieNode() {
		end = false;
		for (int i = 0; i < c_size; i++) child[i] = NULL;
	}
};

class Trie {
	TrieNode* root;
public:
	Trie() { root = new TrieNode();	}
	inline TrieNode * getRoot(){ return root; }
	inline int index(const char &c){ return c - 'a';}

	// Inserts a word into the trie.
	void insert(string word) {
		TrieNode *p = root;
		for (int i = 0; i < word.length(); i++){
			int id = index(word[i]);
			if (!p->child[id]){
				TrieNode *t = new TrieNode();
				p->child[id] = t;
			}
			p = p->child[id];
		}
		p->end = true;
	}

	~Trie() {
		deleteNode(root);
	}

	void deleteNode(TrieNode *root){
		if (!root) return;
		for (int i = 0; i < TrieNode::c_size; i++){
			deleteNode(root->child[i]);
		}
		delete root;
	}

};

const int dx[4] = { 1, -1, 0, 0 };
const int dy[4] = { 0, 0, 1, -1 };
class Solution {
public:
	unordered_set<string> ans;
	vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
		vector<vector<bool> > vis(board.size(), vector<bool>(board[0].size(), 0));
		Trie wordTrie;
		for (int i = 0; i < words.size(); i++)	wordTrie.insert(words[i]);
		for (int i = 0; i < board.size(); i++){
			for (int j = 0; j < board[0].size(); j++){
				if (wordTrie.getRoot()->child[board[i][j] - 'a']){
					vis[i][j] = true;
					string cur; cur.push_back(board[i][j]);
					dfs(i, j, cur, board, vis, wordTrie.getRoot()->child[board[i][j] - 'a']);
					vis[i][j] = false;
				}
			}
		}
		vector<string> res;
		for (auto it = ans.begin(); it != ans.end(); it++){
			res.push_back(*it);
		}
		return res;
	}

	void dfs(int x, int y, string cur, vector<vector<char> >& board, vector<vector<bool> >&vis, TrieNode* p){
		if (p->end) 	ans.insert(cur);
		for (int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (ok(nx, ny, board.size(), board[0].size()) && !vis[nx][ny] && p->child[board[nx][ny] - 'a']){
				vis[nx][ny] = true;
				dfs(nx, ny, cur + board[nx][ny], board, vis, p->child[board[nx][ny] - 'a']);
				vis[nx][ny] = false;
			}
		}
	}

	inline bool ok(int nx, int ny, int m, int n){
		if (nx < 0 || nx >= m || ny < 0 || ny >= n) return false;
		return true;
	}
};

 

218. The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you aregiven the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

题目地址：leetcode The Skyline Problem

题意：给定一些[L,R,H]这样的数组，L,R分别表示矩形起始和终点，H表示高度。 让你求这些矩形的外轮廓中的左端点

思路：

我觉得写不出比 https://briangordon.github.io/2014/08/the-skyline-problem.html 更好的分析了。

我简单的说下大概内容。

就是朴素的方法枚举所有可能的点（每个矩形的左边和右边），然后再枚举包括当前点的所有矩形。 当前的轮廓线取最高的那点。复杂度O(n^2)

更进一步的做法是用堆来看当前最高的高度。

此外由于C++的heap不能删除特定的点，因此用个map标记一下。

还有就是一开始预处理的时候，把左边的高度设为负数，这样就区分开了左右端点。

详见代码。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
	return a.first != b.first ? a.first < b.first : a.second < b.second;
}

class Solution {
public:
	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
		vector<pair<int,int>> heigtht;
		for (int i = 0; i < buildings.size(); i++) {
			heigtht.push_back(make_pair(buildings[i][0], -buildings[i][2]));
			heigtht.push_back(make_pair(buildings[i][1], buildings[i][2]));
		}
		sort(heigtht.begin(), heigtht.end(), cmp);
		vector<pair<int, int>> ans;
		unordered_map<int, int> m;
		priority_queue<int> q;
		int pre = 0;
		q.push(pre);
		for (int i = 0; i < heigtht.size(); i++) {
			if (heigtht[i].second < 0) {
				q.push(-heigtht[i].second);
			}
			else {
				++m[heigtht[i].second];
				while (!q.empty() && m[q.top()] > 0) {
					--m[q.top()];
					q.pop();
				}
			}
			int cur = q.top();
			if (cur != pre) {
				pre = cur;
				ans.push_back(make_pair(heigtht[i].first,cur));
			}
		}
		return ans;
	}
};

 

232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

  • push(x) -- Push element x to the back of queue.
  • pop() -- Removes the element from in front of queue.
  • peek() -- Get the front element.
  • empty() -- Return whether the queue is empty.

Notes:

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

题目地址：leetcode Implement Queue using Stacks

题意：要求你用栈来实现队列。

思路：栈和队列可以说恰好是相反的，栈是后进先出(LIFO)，而队列是先进先出(FIFO)。

所以，这题可以进行push的时候，可以把其中一个栈的元素放到个临时的栈里，然后把新的元素push，接着把放到临时的栈里的数弄回来。比如1234（最右边的为top，这里是4） 放到临时栈为4321，然后原来栈放入5，接着把临时栈的放回来，就是51234

更好的方法是，用两个栈来做，一个负责输入input，一个负责输出output。

  • push:放入input即可
  • peek / pop : 若output为空，则把input中的移入output
  • empty: input 和 output 均为空

对于21354，我们先按顺序放入input，栈为：21354（右边栈顶）

如果要输出，则都放入output，  栈就变成了 45312 （直接反过来了）

接着如果有新的数push,也只要到input即可。直到output为空了，才继续从input拿

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Queue {
    stack<int> input,output;
public:
    // Push element x to the back of queue.
    void push(int x) {
        input.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        peek();
        output.pop();
    }

    // Get the front element.
    int peek(void) {
        if(output.empty()){
            while(!input.empty()){
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return input.empty() and output.empty();
    }
};


Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self._input = []
        self._output = []

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self._input.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        self.peek()
        self._output.pop()

    def peek(self):
        """
        :rtype: int
        """
        if not self._output:
            while self._input:
                self._output.append(self._input[-1])
                self._input.pop()
        return self._output[-1]

    def empty(self):
        """
        :rtype: bool
        """
        return not self._input and not self._output

 

239. Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the _k_numbers in the window. Each time the sliding window moves right by one position.

For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

1
2
3
4
5
6
7
8
9
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

Hint:

  1. How about using a data structure such as deque (double-ended queue)?
  2. The queue size need not be the same as the window’s size.
  3. Remove redundant elements and the queue should store only elements that need to be considered.

题目地址：leetcode Sliding Window Maximum

题意：给定一个数组和一个窗口大小K，要你从数组中按顺序将所有相邻的K个数中最大值输出。

思路：

方法1 单调队列

最暴力的方法当然是枚举起点和接下来的K个数，复杂度O(nk) 这题涉及RMQ等，有方法可以做到O(nlogn)的预处理，然后O(1)的查询，总复杂度O(nlogn) 当然这题用堆也可以。。

线性的时间怎么办？ 那肯定是要观察窗口移动过程中，移出了一个数，然后加入了一个数，我也想到了双端队列。 然而感觉一个长度为K的双端队列没啥用啊？点开hint看到hint2我就醒悟了。

我们维护一个双端队列，第一个元素为最大值，对于窗口移动过程中，新加进来的元素x从队尾向前比较，把小于它的数抛弃掉。（因为x不但大而且在后面，前面的而且小的数是不会为窗口内的最大值的）。此外，若第一个元素已经在窗口外了，那么抛弃第一个即可。

由于队列的长度不可能超过n个，因此复杂度为O(n)。

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) return {};
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.emplace_back(i);
        }
        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < nums.size(); ++i) {
            if (q.front() + k <= i) {
                q.pop_front();
            }
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.emplace_back(i);
            ans.emplace_back(nums[q.front()]);
        }
        return ans;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums: return []
        if k == 1: return nums
        ans = []
        q = deque()
        for i in range(len(nums)):
            if q and q[0] <= i - k:
                q.popleft()
            while q and nums[q[-1]] <= nums[i]:
                q.pop()
            q.append(i)
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

 

方法2 分块法

观察样例：

1
2
3
4
5
6
7
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

如果我们每k个数分一组，那么上述的例子中，[1, 3, -1]为一组， [-3, 5, 3]为一组，[6, 7]为一组

对于\(i \in [0, n - 1]\)来说，若我们可以求得left[i + k - 1]（i所在的组从前往后到i时最大的数）和right[i]（i所在的组从后往前到i时最大的数），那么问题就解决了。

举例来说，若i == 0，则显然是成立的，left[2]和right[0]都是3

若i == 1，则此时滑动窗口[3, -1, -3]跨越了两个分组，left[3] = -3而right[1] =3，所以答案是3。这个时候你应该看出来了，当跨越两个分组的时候，left[i + k - 1] 相当于求下一个分组在当前滑动窗口范围内的最大值，而right[i]则是当前分组在滑动窗口内的最大值.

因此可以写出如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) return {};
        vector<int> left(nums.size(), 0);
        vector<int> right(nums.size(), 0);

        for (std::size_t i = 0; i < nums.size(); ++i) {
            if (i % k == 0) {
                left[i] = nums[i];
            } else {
                left[i] = max(left[i - 1], nums[i]);
            }
        }

        for (int i = static_cast<int>(nums.size()) - 1; i >= 0; --i) {
            if ((i + 1) % k == 0 || i + 1 == nums.size()) {
                right[i] = nums[i];
            } else {
                right[i] = max(right[i + 1], nums[i]);
            }
        }

        vector<int> ans(nums.size() + 1 - k);
        for (int i = 0; i + k <= nums.size(); ++i) {
            ans[i] = max(left[i + k - 1], right[i]);
        }
        return ans;
    }
};

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1: Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2: Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

题目地址：leetcode Flatten Nested List Iterator

题意：给定一个NestedInteger 列表，要求把它展开。 比如[[1,1],2,[1,1]] （里面每一项均为NestedInteger类型）展开为[1,1,2,1,1].

思路：

首先来看看定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]

发现该类有3个函数，是否整数、整数就取整数、列表就取列表。

这题要实现 NestedIterator类要实现3个接口，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NestedIterator(object):

    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        

    def next(self):
        """
        :rtype: int
        """
        

    def hasNext(self):
        """
        :rtype: bool
        """

调用方式为：

1
2
3
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

确保你已经明白题意在往下看。

看到待展开的表达式时嵌套的，就想到，可以用递归开挂~ 水水的1A。

思想是初始化先处理好全部，接下来只要从结果集合中拿就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """
        def solve(nestedList):
            res = []
            for x in nestedList:
                if x.isInteger():
                    res.append(x.getInteger())
                else:
                    res.extend(solve(x.getList()))
            return res

        self.ans = solve(nestedList)[::-1]

    def next(self):
        """
        :rtype: int
        """
        return self.ans.pop()

    def hasNext(self):
        """
        :rtype: bool
        """
        return len(self.ans) != 0

 

但其实递归的方法把所有的解都存起来了，严格的说，不是迭代Iterator，不过给我们实现Iterator提供了思路，就是把递归改成迭代。

怎么改呢~ 用栈啊，当 现在的栈顶的不是整形(那就是List，调用getList)，就把List取出，在压入栈，循环即可。

而实现上，比刚才的递归还要优雅：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NestedIterator(object):
    def __init__(self, nestedList):
        """
        Initialize your data structure here.
        :type nestedList: List[NestedInteger]
        """

        self.stack = nestedList[::-1]

    def next(self):
        """
        :rtype: int
        """
        return self.stack.pop().getInteger()

    def hasNext(self):
        """
        :rtype: bool
        """
        while self.stack and not self.stack[-1].isInteger():
            self.stack.extend(self.stack.pop().getList()[::-1])
        return len(self.stack) != 0

 

352. Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

1
2
3
4
5
6
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?

题目地址：leetcode Data Stream as Disjoint Intervals

题意：要求实现一个数据结构，可以满足不断添加数字，并进行区间的更新。

思路：

这题貌似二分查找也可以，手写BST也可以，不过还是用java的TreeMap实现起来比较方便。

我们根据区间起始位置（就是start）作为BST 的key，对于要添加的数val，查找其左右区间。。  ceil 满足 val < key , floor 满足 key <= val

然后判断其范围进行合并。 感觉没啥好说的。。

PS: C++只有lower_bound和upper_bound， 不像java treemap那么爽 ( ╯□╰ ) Python好像没看过平衡树的样子？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class SummaryRanges {

    TreeMap<Integer, Interval> map;

    public SummaryRanges() {
        map = new TreeMap<Integer, Interval>();
    }

    public void addNum(int val) {
        Integer ceil = map.higherKey(val); // val < key
        Integer floor = map.floorKey(val); // key <= val
        if (floor != null && map.get(floor).end + 1 >= val) {
            if (ceil != null && ceil == val + 1) {
                map.get(floor).end = map.get(ceil).end;
                map.remove(ceil);
            } else
                map.get(floor).end = Math.max(map.get(floor).end, val);
        } else if (ceil != null && ceil == val + 1) {
            map.put(val, new Interval(val, map.get(ceil).end));
            map.remove(ceil);
        } else
            map.put(val, new Interval(val, val));
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(map.values());
    }
}

 

432. All O'one Data Structure

Implement a data structure supporting the following operations:

  1. Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
  2. Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
  3. GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
  4. GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

题目地址：leetcode All O'one Data Structure

题目大意：要求实现一个数据结构，四个接口都需要在O(1)的时间内执行。

思路：

双向链表+hash

链表中每个节点保存对应的val，以及相应的key。

求最大和最小key只需要从头或者尾巴拿即可。

C++

由于c++有双向链表的接口，因此可以直接用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class AllOne {
private:
	struct LinkListNode {
		const int val;
		unordered_set<string> keys;
	};
	list<LinkListNode> linklist;
	unordered_map<string, list<LinkListNode>::iterator> keyToNode;

	void removeNodeKey(string key,list<LinkListNode>::iterator node) {
		node->keys.erase(key);
		if (!node->keys.size())
			linklist.erase(node);
	}

public:
	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
	void inc(string key) {
		auto it = keyToNode.find(key);
		int val = 0;
		if (it != keyToNode.end()) {
			auto next = it->second, node = next++;
			if (next == linklist.end() || next->val != node->val + 1)
				next = linklist.insert(next, { node->val + 1,{ key } });
			else
				next->keys.insert(key);
			removeNodeKey(key, node);
			keyToNode[key] = next;
		}
		else {
			auto node = linklist.begin() != linklist.end() && linklist.begin()->val == 1 ? linklist.begin() : linklist.end();
			if (node == linklist.end())
				node = linklist.insert(linklist.begin(), { 1,{ key } });
			else
				linklist.begin()->keys.insert(key);
			keyToNode[key] = node;
		}
	}

	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
	void dec(string key) {
		auto it = keyToNode.find(key);
		if (it == keyToNode.end()) return;
		auto pre = it->second, node = pre != linklist.begin() ? pre-- : pre;
		if (node->val == 1) {
			keyToNode.erase(key);
			removeNodeKey(key, node);
		}
		else {
			if (node == linklist.begin() || pre->val != node->val - 1)
				pre = linklist.insert(node, { node->val - 1,{ key } });
			else
				pre->keys.insert(key);
			keyToNode[key] = pre;
			removeNodeKey(key, node);
		}
	}

	/** Returns one of the keys with maximal value. */
	string getMaxKey() {
		return linklist.empty() ? "" : *(linklist.rbegin()->keys.begin());
	}

	/** Returns one of the keys with Minimal value. */
	string getMinKey() {
		return linklist.empty() ? "" : *(linklist.begin()->keys.begin());
	}
};

自己写的双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
struct LinkListNode {
	LinkListNode *next, *pre;
	const int val;
	unordered_set<string> keys;
	LinkListNode(int val, string key) :val(val)
	{
		if (!key.empty())
			keys.insert(key);
		next = pre = NULL;
	}
};

class LinkList {
private:
	LinkListNode *head, *tail;

	void insertNode(LinkListNode *pre, LinkListNode *node, LinkListNode *next) {
		pre->next = node;
		node->pre = pre;
		node->next = next;
		next->pre = node;
	}

public:
	LinkList() {
		head = new LinkListNode(0, "");
		tail = new LinkListNode(0, "");
		head->next = tail;
		tail->pre = head;
	}

	~LinkList() {
		while (head != NULL) {
			LinkListNode *p = head;
			head = head->next;
			delete p;
		}
	}

	LinkListNode * removeKey(string key, LinkListNode *node, bool isDec) {
		node->keys.erase(key);
		if (!node->keys.size()) {
			LinkListNode *pre = node->pre, *next = node->next;
			pre->next = next;
			next->pre = pre;
			delete node;
			return pre;
		}
		return isDec ? node->pre : node;
	}

	LinkListNode * inc(string key, int val, LinkListNode * node) {
		if (node == NULL)
			node = head;

		if (node->next->val == val + 1) {
			node = node->next;
			node->keys.insert(key);
			return node;
		}
		else {
			LinkListNode *newNode = new LinkListNode(val + 1, key);
			insertNode(node, newNode, node->next);
			return newNode;
		}
	}

	LinkListNode * dec(string key, int val, LinkListNode * node) {
		if (node == NULL)
			node = head;

		if (node != head && node->val == val - 1) {
			node->keys.insert(key);
			return node;
		}
		else {
			LinkListNode *newNode = new LinkListNode(val - 1, key);
			insertNode(node, newNode, node->next);
			return newNode;
		}
	}

	string getMinKey() {
		if (head->next == tail) return "";
		return *head->next->keys.begin();
	}

	string getMaxKey() {
		if (head->next == tail) return "";
		return *tail->pre->keys.begin();
	}
};



class AllOne {
private:
	LinkList *linklist;
	unordered_map<string, LinkListNode*> keyToNode;
public:
	/** Initialize your data structure here. */
	AllOne() {
		linklist = new LinkList();
	}

	/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
	void inc(string key) {
		auto it = keyToNode.find(key);
		int val = 0;
		LinkListNode * node = NULL;
		if (it != keyToNode.end()) {
			node = it->second;
			val = node->val;
			node = linklist->removeKey(key, node, false);
		}
		keyToNode[key] = linklist->inc(key, val, node);
	}

	/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
	void dec(string key) {
		auto it = keyToNode.find(key);
		if (it == keyToNode.end()) return;
		LinkListNode * node = it->second;
		int val = node->val;
		node = linklist->removeKey(key, node, true);
		if (val == 1) {
			keyToNode.erase(key);
		}
		else {
			keyToNode[key] = linklist->dec(key, val, node);
		}
	}

	/** Returns one of the keys with maximal value. */
	string getMaxKey() {
		return linklist->getMaxKey();
	}

	/** Returns one of the keys with Minimal value. */
	string getMinKey() {
		return linklist->getMinKey();
	}
};

 

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
class AllOne {

    private LinkList linklist = new LinkList();
    private HashMap<String, LinkListNode> keyToNode = new HashMap<>();

    public AllOne() {}

    /**
     * Inserts a new key <Key> with value 1. Or increments an existing key by 1.
     */
    public void inc(String key) {
        LinkListNode node = keyToNode.getOrDefault(key, null);
        int val = 0;
        if (node != null) {
            val = node.val;
            node = linklist.removeKey(key, node, false);
        }
        keyToNode.put(key, linklist.inc(key, val, node));
    }

    /**
     * Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
     */
    public void dec(String key) {
        LinkListNode node = keyToNode.getOrDefault(key, null);
        if (node == null) return;
        int val = node.val;
        node = linklist.removeKey(key, node, true);
        if (val == 1) {
            keyToNode.remove(key);
        } else {
            keyToNode.put(key, linklist.dec(key, val, node));
        }
    }

    /**
     * Returns one of the keys with maximal value.
     */
    public String getMaxKey() {
        return linklist.getMaxKey();
    }

    /**
     * Returns one of the keys with Minimal value.
     */
    public String getMinKey() {
        return linklist.getMinKey();
    }
}

class LinkListNode {
    HashSet<String> keys = new HashSet<>();
    final int val;
    LinkListNode next = null, pre = null;

    public LinkListNode(int val, String key) {
        this.val = val;
        if (key != null)
            keys.add(key);
    }

}

class LinkList {
    private LinkListNode head = new LinkListNode(0, null);
    private LinkListNode tail = new LinkListNode(0, null);

    public LinkList() {
        head.next = tail;
        tail.pre = head;
    }

    public LinkListNode removeKey(String key, LinkListNode node, boolean isDec) {
        node.keys.remove(key);
        if (node.keys.size() == 0) {
            LinkListNode pre = node.pre, next = node.next;
            pre.next = next;
            next.pre = pre;
            return pre;
        }
        return isDec ? node.pre : node;
    }

    private void insertNode(LinkListNode pre, LinkListNode node, LinkListNode next) {
        pre.next = node;
        node.pre = pre;
        node.next = next;
        next.pre = node;
    }

    public LinkListNode inc(String key, int val, LinkListNode node) {
        if (node == null)
            node = head;

        if (node.next.val == val + 1) {
            node = node.next;
            node.keys.add(key);
            return node;
        } else {
            LinkListNode newNode = new LinkListNode(val + 1, key);
            insertNode(node, newNode, node.next);
            return newNode;
        }
    }

    public LinkListNode dec(String key, int val, LinkListNode node) {
        if (node == null)
            node = head;

        if (node != head && node.val == val - 1) {
            node.keys.add(key);
            return node;
        } else {
            LinkListNode newNode = new LinkListNode(val - 1, key);
            insertNode(node, newNode, node.next);
            return newNode;
        }
    }

    public String getMinKey() {
        for (String key : head.next.keys) return key;
        return "";
    }

    public String getMaxKey() {
        for (String key : tail.pre.keys) return key;
        return "";
    }
}


 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
class LinkListNode(object):
    def __init__(self, val):
        self.val = val
        self.keys = set()
        self.pre = self.next = None

class LinkList(object):
    def __init__(self):
        self.head = LinkListNode(0)
        self.tail = LinkListNode(0)
        self.head.next = self.tail
        self.tail.pre = self.head

    def remove_key(self, node, key, is_dec=False):
        node.keys.remove(key)
        if not node.keys:
            _pre, _next = node.pre, node.next
            _pre.next = _next
            _next.pre = _pre
            del node
            return _pre
        return node if not is_dec else node.pre

    def _insert_node(self, _pre, new_node, _next):
        _pre.next = new_node
        new_node.pre = _pre
        _next.pre = new_node
        new_node.next = _next

    def inc_key(self, key, val, node=None):
        if not node:
            node = self.head
        if node.next.val == val + 1:
            node = node.next
            node.keys.add(key)
            return node
        else:
            new_node = LinkListNode(val + 1)
            new_node.keys.add(key)
            self._insert_node(node, new_node, node.next)
            return new_node

    def dec_key(self, key, val, node=None):
        if not node:
            node = self.head

        if node != self.head and node.val == val - 1:
            node.keys.add(key)
            return node
        else:
            new_node = LinkListNode(val - 1)
            new_node.keys.add(key)
            self._insert_node(node, new_node, node.next)
            return new_node

    def get_max_key(self):
        for key in self.tail.pre.keys:
            return key
        return ""

    def get_min_key(self):
        for key in self.head.next.keys:
            return key
        return ""

class AllOne(object):
    def __init__(self):
        self.key_to_node = {}
        self.linklist = LinkList()

    def inc(self, key):
        """
        Inserts a new key <Key> with value 1. Or increments an existing key by 1.
        :type key: str
        :rtype: void
        """
        node = self.key_to_node.get(key, None)
        if node:  # exists
            val = node.val
            node = self.linklist.remove_key(node, key)
        else:
            val = 0
        self.key_to_node[key] = self.linklist.inc_key(key, val, node)

    def dec(self, key):
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        :type key: str
        :rtype: void
        """
        node = self.key_to_node.get(key, None)
        if not node: return
        val = node.val
        node = self.linklist.remove_key(node, key,is_dec=True)
        if val == 1:
            del self.key_to_node[key]
        else:
            self.key_to_node[key] = self.linklist.dec_key(key, val, node)

    def getMaxKey(self):
        """
        Returns one of the keys with maximal value.
        :rtype: str
        """
        return self.linklist.get_max_key()

    def getMinKey(self):
        """
        Returns one of the keys with Minimal value.
        :rtype: str
        """
        return self.linklist.get_min_key()

 503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

1
2
3
4
5
>输入: [1,2,1]
>输出: [2,-1,2]
>解释: 第一个 1 的下一个更大的数是 2；
>数字 2 找不到下一个更大的数； 
>第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

单调栈，首先找到最大的元素下标，向左遍历，同时维护一个栈，这个栈是降序的。

  • 若一个数x，它大于栈顶的元素b，则出栈并把x放入，且x左边的元素的解必然不是b
  • 若一个数x，小于栈顶元素b，则说明它更大的数就是b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if (nums.empty()) {
            return {};
        }
        int max_index = max_element(nums.begin(), nums.end()) - nums.begin();
        stack<int> q;
        q.push(nums[max_index]);
        vector<int> ans(nums.size(), -1);
        for (int i = max_index - 1; i >= 0; --i) {
            while (!q.empty() && q.top() <= nums[i]) {
                q.pop();
            }
            ans[i] = q.empty() ? -1 : q.top();
            q.push(nums[i]);
        }

        for (int i = nums.size() - 1; i > max_index; --i) {
            while (!q.empty() && q.top() <= nums[i]) {
                q.pop();
            }
            ans[i] = q.empty() ? -1 : q.top();
            q.push(nums[i]);
        }
        return ans;
    }
};

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~