leetcode 340 - Longest Substring with At Most K Distinct Characters

https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = “eceba”, k = 2
Output: 3
Explanation: The substring is “ece” with length 3.
Example 2:

Input: s = “aa”, k = 1
Output: 2
Explanation: The substring is “aa” with length 2.

Constraints:

1 <= s.length <= 5 * 10^4
0 <= k <= 50

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
unordered_map<char, int> freq;

int ans = 0;
int i = 0;
for (int j = 0; j < s.size(); j++) {
freq[s[j]]++;

while (freq.size() > k) {
char c = s[i];
if (--freq[c] == 0)
freq.erase(c);
i++;
}

ans = max(ans, j-i+1);
}

return ans;
}
};

leetcode 10 - Regular Expression Matching

https://leetcode.com/problems/regular-expression-matching/

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’ where:

‘.’ Matches any single character.​​​​
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Example 1:

Input: s = “aa”, p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:

Input: s = “aa”, p = “a*”
Output: true
Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:

Input: s = “ab”, p = “.*”
Output: true
Explanation: “.*” means “zero or more (*) of any character (.)”.
Example 4:

Input: s = “aab”, p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.
Example 5:

Input: s = “mississippi”, p = “misis*p.”
Output: false

Constraints:

0 <= s.length <= 20
0 <= p.length <= 30
s contains only lowercase English letters.
p contains only lowercase English letters, ‘.’, and ‘‘.
It is guaranteed for each appearance of the character ‘
‘, there will be a previous valid character to match.

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
class Solution {
public:
vector<vector<int>> memo;

bool helper(string &s, int i, string &p, int j) {
if (j == p.size()) return i == s.size();

if (memo[i][j] != -1)
return memo[i][j];

bool first_match = (i != s.size()) && (s[i] == p[j] || p[j] == '.');

if (j + 1 < p.size() && p[j+1] == '*')
memo[i][j] = helper(s, i, p, j+2) || (first_match && helper(s, i+1, p, j));
else
memo[i][j] = first_match && helper(s, i+1, p, j+1);

return memo[i][j];
}

bool isMatch(string s, string p) {
memo.resize(s.size()+1, vector<int>(p.size()+1, -1));

return helper(s, 0, p, 0);
}
};

leetcode 301 - Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return all the possible results. You may return the answer in any order.

Example 1:

Input: s = “()())()”
Output: [“(())()”,”()()()”]
Example 2:

Input: s = “(a)())()”
Output: [“(a())()”,”(a)()()”]
Example 3:

Input: s = “)(“
Output: [“”]

Constraints:

1 <= s.length <= 25
s consists of lowercase English letters and parentheses ‘(‘ and ‘)’.
There will be at most 20 parentheses in s.

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
class Solution {
public:
vector<string> result;

void get_remove_len(string &s, int &l, int &r) {
for (char c : s) {
if (c == '(')
l++;
else if (c == ')') {
if (l > 0)
l--;
else
r++;
}
}
}

bool is_valid(string &s) {
int count = 0;

for (char c : s) {
if (c == '(')
count++;
else if (c == ')') {
count--;
if (count < 0)
return false;
}
}

return true;
}

void dfs(string &s, int l, int r, int start) {
if (l == 0 && r == 0) {
if (is_valid(s))
result.push_back(s);
return;
}

for (int i = start; i < (int)s.size(); i++) {
if (i != start && s[i] == s[i-1]) continue;

if (s[i] == '(' || s[i] == ')') {
string str = s;
str.erase(i, 1);

if (r > 0 && s[i] == ')')
dfs(str, l, r-1, i);
else if (l > 0 && s[i] == '(')
dfs(str, l-1, r, i);
}
}
}

vector<string> removeInvalidParentheses(string s) {
int l = 0, r = 0;

get_remove_len(s, l, r);

dfs(s, l, r, 0);
return result;
}
};

leetcode 430 - Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

1—2—NULL
|
3—NULL
Example 3:

Input: head = []
Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

1—2—3—4—5—6–NULL
|
7—8—9—10–NULL
|
11–12–NULL
The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Constraints:

The number of Nodes will not exceed 1000.
1 <= Node.val <= 105

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
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/

class Solution {
public:
//return tail
Node *dfs(Node *head) {
if (!head) return NULL;

Node *child = head->child;
Node *next = head->next;

//child相当于left child, next相当于right child, post-order处理
Node *child_tail = dfs(child);
Node *next_tail = dfs(next);

head->child = NULL;

if (child_tail) {
head->next = child;
child->prev = head;
child_tail->next = next;
if (next)
next->prev = child_tail;
}

return next_tail ? next_tail : (child_tail ? child_tail : head);
}

Node* flatten(Node* head) {
dfs(head);
return head;
}
};

leetcode 103 - Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:

Input: root = [1]
Output: [[1]]
Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};

queue<TreeNode *> q;
q.push(root);

vector<vector<int>> all_results;
int step = 0;

while (!q.empty()) {
int n = q.size();

vector<int> result;

//还是按正常顺序enqueue,处理完这个level后再判断是否要reverse
for (int i = 0; i < n; i++) {
TreeNode *node = q.front(); q.pop();
result.push_back(node->val);

if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}

if (step % 2)
reverse(result.begin(), result.end());
all_results.push_back(result);

step++;
}

return all_results;
}
};

leetcode 395 - Longest Substring with At Least K Repeating Characters

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.
Example 2:

Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

Constraints:

1 <= s.length <= 10^4
s consists of only lowercase English letters.
1 <= k <= 105

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
class Solution {
public:
int get_unique(string &s) {
unordered_set<char> char_set;
for (char c : s)
char_set.insert(c);

return char_set.size();
}

int max_window(string &s, int k, int unique) {
int ans = 0;

unordered_map<char, int> freq_map; //char ==> freq

int matched = 0;
int i = 0;

for (int j = 0; j < (int)s.size(); j++) {
if (++freq_map[s[j]] == k)
matched++;

while ((int)freq_map.size() > unique) {
if (freq_map[s[i]]-- == k)
matched--;

if (freq_map[s[i]] == 0)
freq_map.erase(s[i]);

i++;
}

if ((int)freq_map.size() == unique && matched == unique)
ans = max(ans, j-i+1);
}

return ans;
}

int longestSubstring(string s, int k) {
int ans = 0;
int num_unique = get_unique(s);

//可能的解按unique个数分类,枚举所有分类得到最优解
for (int unique = 1; unique <= num_unique; unique++)
ans = max(ans, max_window(s, k, unique));

return ans;
}
};

leetcode 388 - Longest Absolute File Path

https://leetcode.com/problems/longest-absolute-file-path/

Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture:

Here, we have dir as the only directory in the root. dir contains two subdirectories, subdir1 and subdir2. subdir1 contains a file file1.ext and subdirectory subsubdir1. subdir2 contains a subdirectory subsubdir2, which contains a file file2.ext.

In text form, it looks like this (with ⟶ representing the tab character):

dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext
If we were to write this representation in code, it will look like this: “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”. Note that the ‘\n’ and ‘\t’ are the new-line and tab characters.

Every file and directory has a unique absolute path in the file system, which is the order of directories that must be opened to reach the file/directory itself, all concatenated by ‘/‘s. Using the above example, the absolute path to file2.ext is “dir/subdir2/subsubdir2/file2.ext”. Each directory name consists of letters, digits, and/or spaces. Each file name is of the form name.extension, where name and extension consist of letters, digits, and/or spaces.

Given a string input representing the file system in the explained format, return the length of the longest absolute path to a file in the abstracted file system. If there is no file in the system, return 0.

Example 1:

Input: input = “dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext”
Output: 20
Explanation: We have only one file, and the absolute path is “dir/subdir2/file.ext” of length 20.
Example 2:

Input: input = “dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext”
Output: 32
Explanation: We have two files:
“dir/subdir1/file1.ext” of length 21
“dir/subdir2/subsubdir2/file2.ext” of length 32.
We return 32 since it is the longest absolute path to a file.
Example 3:

Input: input = “a”
Output: 0
Explanation: We do not have any files, just a single directory named “a”.
Example 4:

Input: input = “file1.txt\nfile2.txt\nlongfile.txt”
Output: 12
Explanation: There are 3 files at the root directory.
Since the absolute path for anything at the root directory is just the name itself, the answer is “longfile.txt” with length 12.

Constraints:

1 <= input.length <= 104
input may contain lowercase or uppercase English letters, a new line character ‘\n’, a tab character ‘\t’, a dot ‘.’, a space ‘ ‘, and digits.

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
class Solution {
public:
int lengthLongestPath(string input) {
int ans = 0;
bool is_file = false;
int cur_len = 0;
int depth = 0;
vector<int> depth_len;

for (int i = 0; i <= input.size(); i++) {
char c = input[i];

if (c == '\0' || c == '\n') {
if (is_file) {
if (depth == 0)
ans = max(ans, cur_len);
else
ans = max(ans, depth_len[depth-1] + cur_len);
} else {
int len = cur_len + (depth == 0 ? 0 : depth_len[depth-1]) + 1;
if (depth == depth_len.size())
depth_len.push_back(len);
else
depth_len[depth] = len;
}

is_file = false;
cur_len = 0;
depth = 0;

} else if (c == '\t') {
depth++;
} else {
cur_len++;
if (c == '.')
is_file = true;
}
}

return ans;
}
};

leetcode 468 - Validate IP Address

https://leetcode.com/problems/validate-ip-address/
https://leetcode.com/problems/validate-ip-address/discuss/238511/C%2B%2B-split

Given a string IP, return “IPv4” if IP is a valid IPv4 address, “IPv6” if IP is a valid IPv6 address or “Neither” if IP is not a correct IP of any type.

A valid IPv4 address is an IP in the form “x1.x2.x3.x4” where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, “192.168.1.1” and “192.168.1.0” are valid IPv4 addresses but “192.168.01.1”, while “192.168.1.00” and “192.168@1.1“ are invalid IPv4 addresses.

A valid IPv6 address is an IP in the form “x1:x2:x3:x4:x5:x6:x7:x8” where:

1 <= xi.length <= 4
xi is a hexadecimal string which may contain digits, lower-case English letter (‘a’ to ‘f’) and upper-case English letters (‘A’ to ‘F’).
Leading zeros are allowed in xi.
For example, “2001:0db8:85a3:0000:0000:8a2e:0370:7334” and “2001:db8:85a3:0:0:8A2E:0370:7334” are valid IPv6 addresses, while “2001:0db8:85a3::8A2E:037j:7334” and “02001:0db8:85a3:0000:0000:8a2e:0370:7334” are invalid IPv6 addresses.

Example 1:

Input: IP = “172.16.254.1”
Output: “IPv4”
Explanation: This is a valid IPv4 address, return “IPv4”.
Example 2:

Input: IP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
Output: “IPv6”
Explanation: This is a valid IPv6 address, return “IPv6”.
Example 3:

Input: IP = “256.256.256.256”
Output: “Neither”
Explanation: This is neither a IPv4 address nor a IPv6 address.
Example 4:

Input: IP = “2001:0db8:85a3:0:0:8A2E:0370:7334:”
Output: “Neither”
Example 5:

Input: IP = “1e1.4.5.6”
Output: “Neither”

Constraints:

IP consists only of English letters, digits and the characters ‘.’ and ‘:’.

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
class Solution {
public:
//API: count, getline
vector<string> split(string &str, char separator) {
istringstream iss(str);
vector<string> parts;

string part;
while (getline(iss, part, separator))
parts.push_back(part);

return parts;
}

bool isIPv4(string &IP) {
vector<string> parts = split(IP, '.');
if (parts.size() != 4)
return false;

for (auto &part : parts) {
if (part.empty() || part.size() > 3 || (part.size() > 1 && part[0] == '0'))
return false;

for (char c : part) {
if (!isdigit(c))
return false;
}

if (stoi(part) > 255)
return false;
}

return true;
}

bool isIPv6(string &IP) {
vector<string> parts = split(IP, ':');
if (parts.size() != 8)
return false;

for (auto &part : parts) {
if (part.empty() || part.size() > 4)
return false;

for (char c : part) {
if (!isdigit(c) && (!isalpha(c) || toupper(c) > 'F'))
return false;
}
}

return true;
}

string validIPAddress(string IP) {
if (count(IP.begin(), IP.end(), '.') == 3) {
if (isIPv4(IP))
return "IPv4";
} else if (count(IP.begin(), IP.end(), ':') == 7) {
if (isIPv6(IP))
return "IPv6";
}

return "Neither";
}
};

leetcode 449 - Serialize and Deserialize BST

https://leetcode.com/problems/serialize-and-deserialize-bst/
https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93167/Concise-C%2B%2B-19ms-solution-beating-99.4

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]
Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is guaranteed to be a binary search tree.

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
void serialize(TreeNode *root, string &output) {
if (!root) return;

char *p = (char *)&root->val;
for (int i = 0; i < sizeof(int); i++)
output.push_back(p[i]);

serialize(root->left, output);
serialize(root->right, output);
}

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string output;
serialize(root, output);
return output;
}

TreeNode *deserialize(string &data, int &i, int min_val, int max_val) {
if (i == data.size()) return NULL;

int val = *(int *)&data[i];
if (val < min_val || val > max_val)
return NULL;

TreeNode *root = new TreeNode(val);
i += sizeof(int);
root->left = deserialize(data, i, min_val, val);
root->right = deserialize(data, i, val, max_val);
return root;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int i = 0;
return deserialize(data, i, INT_MIN, INT_MAX);
}
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

leetcode 716 - Max Stack

https://leetcode.com/problems/max-stack/

Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.

Implement the MaxStack class:

MaxStack() Initializes the stack object.
void push(int x) Pushes element x onto the stack.
int pop() Removes the element on top of the stack and returns it.
int top() Gets the element on the top of the stack without removing it.
int peekMax() Retrieves the maximum element in the stack without removing it.
int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1:

Input
[“MaxStack”, “push”, “push”, “push”, “top”, “popMax”, “top”, “peekMax”, “pop”, “top”]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5); // [5] the top of the stack and the maximum number is 5.
stk.push(1); // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5); // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top(); // return 5, [5, 1, 5] the stack did not change.
stk.popMax(); // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top(); // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop(); // return 1, [5] the top of the stack and the max element is now 5.
stk.top(); // return 5, [5] the stack did not change.

Constraints:

-10^7 <= x <= 10^7
At most 104 calls will be made to push, pop, top, peekMax, and popMax.
There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call?

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
class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {

}

void push(int x) {
stk.push(x);
if (max_stk.empty()) //注意:判断非空
max_stk.push(x);
else
max_stk.push(max(x, max_stk.top()));
}

int pop() {
int val = stk.top();
stk.pop();
max_stk.pop();
return val;
}

int top() {
return stk.top();
}

int peekMax() {
return max_stk.top();
}

//O(N)
int popMax() {
int max_val = max_stk.top();

stack<int> tmp;
while (!stk.empty() && stk.top() != max_val) {
tmp.push(stk.top());
stk.pop();
max_stk.pop();
}

stk.pop();
max_stk.pop();

while (!tmp.empty()) {
push(tmp.top());
tmp.pop();
}

return max_val;
}

private:
stack<int> stk, max_stk;
};

class MaxStack {
public:
/** initialize your data structure here. */
MaxStack() {

}

//O(logN)
void push(int x) {
data.push_front(x);
it_map[x].push_back(data.begin());
}

//O(logN)
int pop() {
int val = data.front(); data.pop_front();
it_map[val].pop_back();
if (it_map[val].empty())
it_map.erase(val);
return val;
}

//O(1)
int top() {
return data.front();
}

//O(logN)
int peekMax() {
return it_map.rbegin()->first;
}

//O(logN)
int popMax() {
auto it = it_map.rbegin();
int val = it->first;
auto data_it = it->second.back();
data.erase(data_it);
it->second.pop_back();
if (it->second.empty())
it_map.erase(it->first);
return val;
}
private:
list<int> data;
map<int, vector<list<int>::iterator>> it_map;
};

/**
* Your MaxStack object will be instantiated and called as such:
* MaxStack* obj = new MaxStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->peekMax();
* int param_5 = obj->popMax();
*/