1201. Next Greater Element II

class Solution { public: /** * @param nums: an array * @return: the Next Greater Number for every element */ vector<int> nextGreaterElements(vector<int> &nums) { // Write your code here const int n = nums.size(); vector<int> res(n, -1); std::stack<int> stk; for(int i = 0; i < 2 * n; i++){ while(!stk.empty() && nums[stk.top()] < nums[i % n]){ res[stk.top()] = nums[i % n]; stk.pop(); } stk.push(i % n); } return res; } };

Comments

Post a Comment

Popular posts from this blog

Amazon OA 763. Partition Labels

class Solution { public:     vector<int> partitionLabels(string S) {         // 这是个好题         unordered_map<char, int> mp;         vector<int> res;         const int size = S.size();         if(size == 0){             return res;         }         for(int i = 0; i < size; i++){             mp[S[i]] = i;         }         int start = 0, end = 0;         for(int i = 0; i < size; i++){             end = max(end, mp[S[i]]);             if(i == end){                 res.push_back(i - start + 1);                 start = end + 1;     ...
Read more

1427. Split Array into Fibonacci Sequence

Description 中文 English Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579]. Formally, a Fibonacci-like sequence is a list F of non-negative integers such that: 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type); F.length >= 3; and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2. Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself. Return any Fibonacci-like sequence split from S, or return [] if it cannot be done. 1 <= S.length <= 200 S contains only digits. Have you met this question in a real interview?    Yes Problem Correction Example Example 1: Input: "123456579" Output: [123,456,579] Example 2: Input: "11235813" Output: [1,1,2,3,5,8,13] Example 3: Input: "112358130" Output: [] Ex...
Read more

1464. The K-th Combination

很巧妙的办法， 还有一个求 组合数目的方法 Code ( Language :C++) Edit class Solution { public : /** * @param n: The integer n * @param k: The integer k * @return: Return the combination */ vector < int > getCombination( int n, int k) { vector < vector < int >> C(n+ 1 , vector < int >(n+ 1 , 0 )); for ( int i = 0 ; i <= n; ++i) { C[i][ 0 ] = C[i][i] = 1 ; } // Compute C(m, n) using C(m, n) = C(m-1, n-1)+C(m-1, n). for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j < i; ++j) { C[i][j] = C[i -1 ][j -1 ] + C[i -1 ][j]; } } vector < int > ans; int curr_index = 1 ; for ( int i = 1 ; i <= n/ 2 ; ++i) { int base = C[n-curr_index][n/ 2 -i]; // Search for next digit in ans. while (k > base) { curr_index++; b...
Read more