1. 496. Next Greater Element I
暴力的话，复杂度也就1000 * 1000 = 1e6, 在1s的时限内完全可以。
当然，有许多优化方法，利用stack维护递减序列的方法， 见这里
2. 506. Relative Ranks
这个是水题，直接排序，处理一下边界问题，输出就可以。
1 class Solution { 2 public: 3 vector findRelativeRanks(vector & nums) { 4 int n = nums.size(); 5 vector a(n); 6 for (int i = 0; i < n; i++) a[i] = i; 7 sort(a.begin(), a.end(), [&](int x, int y) { 8 return nums[x] > nums[y]; 9 });10 vector res(n);11 string b[3] = { "Gold Medal", "Silver Medal", "Bronze Medal"};12 for (int i = 0; i < min(3, n); i++) {13 res[a[i] ] = b[i];14 }15 for (int i = 3; i < n; i++) {16 //stringstream ss;17 //ss << i + 1;18 res[a[i]] = to_string(i + 1);19 }20 return res;21 }22 }; 3. 503. Next Greater Element II
a. 这题，暴力的话1e4 * 1e4 = 1e8, 卡时限，每次的运算也很简单， 在leetcode上面一般能过。
但是，应该寻找更优的方法。
b. 先说一下，我的蠢办法，我居然拿线段树去做了，复杂度nlognlogn,应该是这个吧！我用线段树维护区间的最大值，预先建立好线段树，使得查询任意区间的最大值都是logn，然后，对一个数，对剩下的区间进行二分查找，求满足第一个满足区间的最大值大于该数。可以ac。
我的代码，（写的有点多，有点杀鸡焉用牛刀的感觉，算是复习下线段树的写法，其实rmq，sparse table也可以满足要求）。
1 int a[50000]; 2 vector f; 3 int n; 4 void bt(int o, int l, int r) { 5 //cout << o << endl; 6 if(l == r) { 7 a[o] = f[l - 1]; 8 //cout << l - 1 << " " << f[l - 1] << endl; 9 } else {10 int mid = (l + r) >> 1;11 bt(o * 2, l, mid);12 bt(o * 2 + 1, mid + 1, r);13 a[o] = max(a[o * 2], a[o * 2 + 1]);14 }15 //cout << o << " " << a[o] << endl;16 }17 int dx, dy;18 //int cnt;19 int ask(int o, int l, int r) {20 //cout << o << " " << l << " " << r << endl;21 //cnt++;22 //if(cnt >= 5) return 0;23 if(dx > dy) return INT_MIN;24 if(r < dx || l > dy) return INT_MIN;25 if(dx <= l && r <= dy) {26 return a[o];27 } else {28 int mid = (l + r) >> 1;29 bool f1, f2;30 int a1, a2;31 f1 = f2 = 0;32 // if(mid <= dy) {33 // f1 = 1;34 // a1 = ask(o * 2, l, mid);35 // }36 // if(mid + 1 >= dx) {37 // f2 = 1;38 // a2 = ask(o * 2 + 1, mid + 1, r);39 // }40 a1 = ask(o * 2, l, mid);41 a2 = ask(o * 2 + 1, mid + 1, r);42 int res = INT_MIN;43 //if(f1) res = max(res, a1);44 //if(f2) res = max(res, a2);45 res = max(a1, a2);46 return res;47 }48 }49 int work(int tar, int left, int right) {50 int p = left;51 while(left < right) {52 int mid = (left + right) / 2;53 dx = p, dy = mid;54 int t = ask(1, 1, n);55 if(t > tar) {56 right = mid;57 } else {58 left = mid + 1;59 }60 }61 dx = p, dy = left;62 return ask(1, 1, n);63 }64 vector nextGreaterElements(vector & nums) {65 f = nums;66 n = nums.size();67 bt(1, 1, n);68 vector res(n);69 //cout << "asd" << endl;70 for (int i = 1; i <= n; i++) {71 int tar = nums[i - 1];72 dx = i + 1, dy = n;73 int x = ask(1, 1, n);74 //cout << x << endl;75 //return res;76 dx = 1, dy = i - 1;77 int y = ask(1, 1, n);78 cout << x << " " << y << endl;79 80 if(x > tar) {81 res[i - 1] = work(tar, i + 1, n);82 } else if(y > tar) {83 res[i - 1] = work(tar, 1, i - 1);84 } else {85 res[i - 1] = -1;86 }87 cout << i << endl;88 //return res;89 }90 return res;91 } c. 这个题跟第一题差不多，其实还是稍微不同的，一种是利用stack维护单调递减的性质，循环的解决办法，就是创建2倍的原数组长度，这应该算通用的解决办法。见这里：
其实，stack优化的题目，leetcode有一类这样的题目，这种解法不容易想出来，需要仔细分析性质，我不是很熟练，有时间练习学习一下。好像有好几道，反正不是很好做！
d. 还有一种解法，我看的排名第一的解法，利用这样的性质，用res[i]记录最后的结果，a[i]代表原数组，i < j, 我们计算res[i]的时候，如果i < j, a[j] <= a[i], 可以先计算出res[j], 然后怎么考虑使用res[j]进行优化，其实 j 到 res[j] 之间的数字可以直接跳过，我们可以不直接保存res[j], 而是保存res[j]的下标，利用这个下标进行跳转。可以利用这个性质，进行优化。复杂度分析：不会分析。
代码：
1 class Solution { 2 int n; 3 vector a, f; 4 public: 5 int calc(int x) 6 { 7 int &ans = f[x]; 8 if(ans >= -1) 9 return ans;10 if(ans == -3)11 return ans = -1;12 ans = -3;13 int y;14 for(y = (x + 1) % n; y != -1 && a[x] >= a[y]; y = calc(y));15 return ans = y;16 }17 vector nextGreaterElements(vector & nums) {18 a = nums; n = a.size();19 f.resize(n, -2);20 vector aa;21 for(int i = 0; i < n; i++)22 {23 calc(i);24 if(f[i] == -1) aa.push_back(-1);25 else aa.push_back(a[f[i]]);26 }27 return aa;28 }29 }; 4. 498. Diagonal Traverse
我的做法是：使用辅助空间记录每一行的起始位置，注意一下方向和边界条件。
更好的做法是：空间复杂度O(1)的， 维护每次转移的坐标，代码速度很快！