盛最多水的容器

给定 n 个非负整数 a_1，_a_2，…，_a_n，每个数代表坐标中的一个点 (_i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

class Solution {
public:
int maxArea(vector& a){
vector v[20100];
int up = 0;
int mx = 0, mn = 2e9;
int ans = 0;

    int pos = 0;  
    for (auto u : a) v\[u\].push\_back(++pos), up = max(up, u);

    for (int i = up; i; --i){  
        if (v\[i\].size() > 0){  
            for (auto u : v\[i\]){  
                mx = max(mx, u);  
                mn = min(mn, u);  
            }  
            ans = max(ans, (mx - mn) \* i);  
        }  
    }

    return ans;  
}  

};

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

class Solution {
public:
int majorityElement(vector& nums) {
int cnt = 0, now = 0;
for (auto u : nums){
if (cnt == 0) now = u, cnt = 1;
else cnt += (u == now ? 1 : -1);
}
return now;
}
};

LRU缓存机制

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

#define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second

class LRUCache {
private:
int up;
int cnt;
list< pair> queue;
unordered_map< int, list>::iterator> mp;

public:  
    LRUCache(int capacity){  
        up = capacity;  
        mp.clear();  
        cnt = 0;

    }

    int get(int key){  
        int ret = -1;  
        auto p = mp.find(key);  
        if (p != mp.end()){  
            ret = p -> se -> se;  
            queue.erase(p -> se);  
            queue.push\_front(MP(key, ret));  
            p -> se = queue.begin();  
        }

        return ret;

    }

    void put(int key, int value){  
        auto p = mp.find(key);  
        if (p != mp.end()){  
            queue.erase(p -> se);  
        }

        else if (cnt == up){  
            int delkey = queue.back().fi;  
            queue.pop\_back();  
            mp.erase(delkey);  
        }

        else ++cnt;

        queue.push\_front(MP(key, value));  
        mp\[key\] = queue.begin();  
    }  

};

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

class MinStack {
private:
stack s, t;
public:
/** initialize your data structure here. */
MinStack(){

    }

    void push(int x){  
        s.push(x);  
        if (t.empty() || x <= t.top()){  
            t.push(x);  
        }

    }

    void pop(){  
        int now = s.top();  
        s.pop();  
        if (!t.empty() && t.top() == now){  
            t.pop();  
        }

    }

    int top(){  
        return s.top();

    }

    int getMin(){  
        return t.top();

    }  

};