Heap Sort

Heap Sort
The running complexity of BuildHeap is O(n)
http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
"Thus the lesson to be learned is that when designing algorithms that operate on trees, it is important to be most efficient on the bottommost levels of the tree (as BuildHeap is) since that is where most of the weight of the tree resides"

Another simple analysis:
we can skip half of the nodes at the height 0, which has n / 2 nodes
at height 1: n / 4 * 1
at height 2: n / 8 * 2
at height 3: n / 16 * 3
...
at height lgn: 1 * lgn

for bottom 3 levels: n / 4 + n / 8 * 2 + n / 16 * 3 = 11 / 16 * n
for bottom 4 levels: 11 / 16 + 4 / 32 = 13 / 16 * n
for bottom 5 levels: 13 / 16 + 5 / 64 = 47 / 64 * n
for bottom 6 levels: 47 / 64 + 6 / 128 = 100 / 128 * n
...
you can see that it will never be greater than n. That's why it is linear

Day 85, #97, Interleaving String

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
------------------------------------------------------
Solution #1, straight forward recursion 

class Solution {
public:
    bool isInter(string s1, int i1, string s2, int i2, string s3, int i3) {
        if (i3 == s3.length()) {
            return true;
        }
        
        if (i1 < s1.length() && s1[i1] == s3[i3] && isInter(s1,i1 + 1,s2,i2,s3,i3 + 1)) {
            return true;
        }
        
        if (i2 < s2.length() && s2[i2] == s3[i3] && isInter(s1,i1,s2,i2 + 1,s3,i3 + 1)) {
            return true;
        }
        
        return false;
        
    }

    bool isInterleave(string s1, string s2, string s3) {
        return isInter(s1,0,s2,0,s3,0);
    }
};

Solution #2 DP, similar logi. dp[i][j] means if s1[0 : i] and s2[0 : j] can match s3[0 : i + j + 1]
不用检查s3[0]是因为，只有在s1或s2长度为0时，s3[0]才有被检查的必要，这我们已经在initialization的时候已经做过 
***一定要想清楚 dp[i][j] 所代表的意思***

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 + len2 != s3.length()) return false;
        
        // check empty strings
        if (len1 == 0) {
            if (s2 == s3) {
                return true;
            }else {
                return false;
            }
        }
        if (len2 == 0) {
            if (s1 == s3) {
                return true;
            }else {
                return false;
            }
        }
        
        vector<vector<bool> > dp(len1 + 1,vector<bool>(len2 + 1,false));
        
        // initialize dp
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            if (s1[i - 1] == s3[i - 1]) {
                dp[i][0] = true;
            }else {
                break;
            }
        }
        
        for (int i = 1; i <= len2; i++) {
            if (s2[i - 1] == s3[i - 1]) {
                dp[0][i] = true;
            }else {
                break;
            }
        }
        
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if (s1[i] == s3[i + j + 1] && dp[i][j + 1]) {
                    dp[i + 1][j + 1] = true;
                }
                
                if (s2[j] == s3[i + j + 1] && dp[i + 1][j]) {
                    dp[i + 1][j + 1] = true;
                }
            }
        }
        
        return dp[len1][len2];
    }
};

可以简化为O(n) space, 就不写了

Day 84, #87, Scramble String

Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
-------------------------------------------------------------
Solution #1 recursive

bool scramble(string s1,string s2) {
    if (s1 == s2) return true;    
    string t1 = s1,t2 = s2;
    sort(t1.begin(),t1.end());
    sort(t2.begin(),t2.end());
    if (t1 != t2) return false;
    
    for (int i = 1; i < s1.length(); i++) {
        string p1 = s1.substr(0,i), p2 = s1.substr(i);
        string q1 = s2.substr(0,i), q2 = s2.substr(i); 
        string q3 = s2.substr(s2.length() - i), q4 = s2.substr(0,s2.length() - i);
        
        if ((scramble(p1,q1) && scramble(p2,q2)) || (scramble(p1,q3) && scramble(p2,q4))) return true;
    }
    return false;
}

Solution #2 recursive + memo
找出s1所有的scrambled strings，然后一一对比

class Solution {
public:
    unordered_map<string,vector<string>> dic;
    void combine(vector<string> &rt,vector<string> &v1,vector<string> &v2) {
        for (string s1 : v1) {
            for (string s2 : v2) {
                rt.push_back(s1 + s2);
                rt.push_back(s2 + s1);
            }
        }
    }

    vector<string> permutation(string s) {
        vector<string> rt;
        if (s.length() == 1) {
            rt.push_back(s);
        }
    
        for (int i = 1; i < s.length(); i++) {
            string s0 = s.substr(0,i);
            string s1 = s.substr(i);
            vector<string> v1,v2; 
            if (dic.find(s0) != dic.end()) {
                v1 = dic[s0];
            }else {
                v1 = permutation(s0);
                dic[s0] = v1;   
            }
            
            if (dic.find(s1) != dic.end()) {
                v2 = dic[s1];
            }else {
                v2 = permutation(s1);
                dic[s1] = v2;
            }
            combine(rt,v1,v2);
        }
        
        return rt;
    }

    bool isScramble(string s1, string s2) {
        vector<string> rt = permutation(s1);
        for (string s : rt) {
            if (s == s2) return true;
        }
        
        return false;
    }
};

Solution #3 3-dimensional DP
dp[length][index at s1][index at s2]
int the most inner loop, delimiter breaks string in k - 1 different ways. same logic as recursive
注意loop里的终止条件

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int len = s1.length();
        
        vector<vector<vector<bool> > > dp(len,vector<vector<bool> >(len,vector<bool>(len,false)));
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s1[i] == s2[j]) {
                    dp[0][i][j] = true;
                } 
            }
        }
        
        for (int k = 2; k <= len; k++) {
            for (int i = 0; i <= len - k; i++) {
                
                for (int j = 0; j <= len - k; j++) {

                    for (int delimiter = 1; delimiter < k; delimiter++) {
                        
                        if (dp[delimiter - 1][i][j] && dp[k - delimiter - 1][i + delimiter][j + delimiter]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                            
                        if (dp[delimiter - 1][i][j + k - delimiter] && dp[k - delimiter - 1][i + delimiter][j]) {
                            dp[k - 1][i][j] = true;
                            break;
                        }
                        
                    }
                }
                
            }
            
        }
    
        return dp[len - 1][0][0];
    }
};

Day 83, #85, Maximal Rectangle

Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

--------------------------------------------
方法1：O(m * n) 解法来自google，借用了上一题Largest Rectangle Area的代码
将每一行都看做x轴，在每一个列上的连续1的个数则为当前列的y值，计算出当前行的最大矩形面积

class Solution {
public:
    // from the question Largest Rectangle Area
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() == 0) return 0;
        vector<int> heights(matrix[0].size(),0);
        int largest = 0;
        
        for (int row = 0; row < matrix.size(); row++) {
            for (int col = 0; col < matrix[0].size(); col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                }else {
                    heights[col] = 0;
                }
            }
            largest = max(largest, largestRectangleArea(heights));
        }
        
        return largest;
    }
};

方法2：O(m * n * m)
dp[i][j]存的是以（i,j）为起点往右，在该行上连续的1的个数

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n + 1,0));
        
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = dp[i][j + 1] + 1;
                }
            }
        }
        
        int largest = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int width = dp[i][j];
                for (int k = i; k < m && width > 0; k++) {
                    width = min(dp[k][j],width);
                    largest = max(largest,width * (k - i + 1));
                }
            }
        }
        
        return largest;
    }
};

方法3：COME_BACK
height[i]是在（i, j）上1的高度，如果matrix[i][j] = 0，则height[i] = 0
left[i]是底边包含(i, j)，高度为height[i]矩阵的最左边的index，right[i]类似
（找个例子，走一边就信服了）

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> left(n,0);
        vector<int> right(n,n - 1);
        vector<int> height(n,0);
        int largest = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                }else {
                    height[j] = 0;
                }
            }
            
            int furLeft = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = max(furLeft,left[j]);
                }else {
                    furLeft = j + 1;
                    left[j] = 0;
                }
            }
            
            int furRight = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = min(furRight,right[j]);
                }else {
                    furRight = j - 1;
                    right[j] = n - 1;
                }
            }
            
            for (int j = 0; j < n; j++) {
                largest = max(largest,height[j] * (right[j] - left[j] + 1));
            }
        }
        
        return largest;
    }
};

Day 82, #84, Largest Rectangle in Histogram

Largest Rectangle in Histogram

 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

----------------------------------------------------------
for each single bar, calculate the largest rectangle that has the same height as the bar,
OJ Time Limit Exceeded

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int largest = 0;
        
        for (int i = 0; i < height.size(); i++) {
            int left = i - 1, right = i + 1;
            int length = 1;
            while (left >= 0 && height[left] >= height[i]) {
                length++;
                left--;
            }
            
            while (right < height.size() && height[right] >= height[i]) {
                length++;
                right++;
            }
            
            largest = max(largest,length * height[i]);
        }
        
        return largest;
    }
};

Solution #2
网上讲解很多，请google
要点
#1 原数组末尾插入0是为了清空并计算stack内所剩的数
#2 第18行: (topBar - st.top() - 1) + (i - topBar) = i - st.top() -  1
- topBar左边：因为从st.top（）到topBar之间的长方形都高于topBar，当计算以topBar为高度的面积时得包含之前的长方形
- topBar右边：到当前的i为止，所有的长方形都大于或等于topBar
#3 当stack为空时，说明之前所有经历过的长方形都高于topBar. 因为在某一个index时，stack里面比当前小的永远不会被pop出去
#4 stack所存的是index
#5 stack里的高度永远为递增
例子：{4,2,0,3,2,5}
情况1：

情况2：

情况3：

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }
};

Day 81, #81, Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
--------------------------------------------------------------------------
与I同样的思路，不同点是增加了1个if判断来解决重复的问题
重复的情况#1： start，mid，end 3处都相等，如111111111111112111。此时左右两半都需要检测，worst cast O(n)
重复的情况#2：仅start或者end跟mid相等，如4444123，此时原有代码也可解决

class Solution {
public:
    bool searchInRotated(int A[], int start, int end, int target) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (A[mid] == target) {
            return true;
        }
        
        // ------ to handle duplicates ---- 
        if (A[start] == A[mid] && A[start] == A[end]) {
            return searchInRotated(A,start,mid - 1,target) || searchInRotated(A,mid + 1,end,target);
        }
        
        if (A[start] <= A[mid]) {
            if (A[start] <= target && target <= A[mid]) {
                return searchInRotated(A,start,mid - 1,target);
            }else {
                return searchInRotated(A,mid + 1,end,target);
            }
        }else {
            if (A[mid] <= target && target <= A[end]) {
                return searchInRotated(A,mid + 1,end,target);
            }else {
                return searchInRotated(A,start,mid - 1,target);
            }
        }
        
    }

    bool search(int A[], int n, int target) {
        return searchInRotated(A,0,n - 1,target);
    }
};

Solution #2, iterative(to do)

Day 80, #60, Permutation Sequence

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
-----------------------------------------------------------------------------
Factorial. Lay out permutations, you will see the pattern
将k设为0-base

class Solution {
public:
    int getFactorial(int n) {
        int rt = 1;
        for (int i = 1; i <= n; i++) {
            rt *= i;
        }
        
        return rt;
    }

    int getNextNumber(vector<bool> &nums, int section) {
        for (int i = 0; i < nums.size(); i++) {
            if (section == 0 && nums[i] == false) {
                nums[i] = true;
                return i;
            }
            if (nums[i] == false) {
                section--;
            }
        }
    }

    string getPermutation(int n, int k) {
        int factorial = getFactorial(n);
        string rt = "";
        vector<bool> nums(n,false);
        k--;
        for (int i = n; i > 0; i--) {
            factorial /= i;
            int section = k / factorial;
            k = k % factorial;
            char c = getNextNumber(nums,section) + '1';
            rt += c;
        }
        
        return rt;
    }
};

Day 79, #44, Wildcard Matching

Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

---------------------------------------------------------------
Solution #1 recursion, OJ time limit exceeded

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*p == *s || *p == '?') {
            return isMatch(s + 1, p + 1);
        }
        
        if (*p == '*') {
            while (*s != '\0') {
                if(isMatch(s,p + 1)) {
                    return true;
                }
                s++;
            }
        }
        
        return false;
    }
};

Solution #2, dp with 2d arrays,

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        
        dp[0][0] = true;
        for (int i = 0; i < m; i++) {
         if (p[i] != '*') break;
            dp[i + 1][0] = true;
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] && (p[i] == s[j] || p[i] == '?')) {
                    dp[i + 1][j + 1] = true;
                }else if (p[i] == '*') {
                    if (dp[i][j + 1] || dp[i + 1][j]) {
                        dp[i + 1][j + 1] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
};

改良版DP，用了一个一维数组，当*p == '*',dp[j]只取决于dp[j - 1]，过不了最后一个test case

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = p.length(), n = s.length();
        vector<bool> dp(n + 1,false);
        bool diag = true;
        dp[0] = true;
        
        for (int i = 0; i < m; i++) {
            diag = dp[0];
            for (int j = 0; j < n; j++) {
                if (diag && (p[i] == s[j] || p[i] == '?')) {
                    diag = dp[j + 1];
                    dp[j + 1] = true;
                }else if (p[i] == '*') {
                    diag = dp[j + 1];
                    if (dp[j] || dp[j + 1]) {
                        dp[j + 1] = true;
                    }
                }else {
                    diag = dp[j + 1];
                    dp[j + 1] = false;
                }
            }
            if (p[i] == '*' && dp[0]) {
                dp[0] = true;
            }else {
                dp[0] = false;
            }
            
        }
        
        return dp[n];
    }
};

Solution #3, constant space
star用来记录最近*的位置，index用来记录当前*匹配成功后s的位置。*之前全部匹配成功，不用再重复检测。*之后如果匹配失败，回头从star + 1 和 index重新匹配，每匹配失败一次，index增加一位。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char *star = NULL;
        const char *index = s;
        
        while (*s != '\0') {
            if (*s == *p || *p == '?') {
                s++;
                p++;
            }else if (*p == '*') {
                star = p;
                p++;
                index = s;
            }else if (star != NULL) {
                p = star + 1;
                index++;
                s = index;
            }else return false;
        }
        
        while (*p == '*') {
            p++;
        }
        
        return *p == '\0';
    }
};

Java,2维dp

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
            
        for (int i = 0; i < p.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp.get(i).get(j) && (s.charAt(j) == p.charAt(i) || p.charAt(i) == '?')) {
                    dp.get(i + 1).set(j + 1, true);
                } else if (p.charAt(i) == '*' && (dp.get(i).get(j + 1) || dp.get(i + 1).get(j))) {
                    dp.get(i + 1).set(j + 1, true);
                }
            }
        }
        
        return dp.get(p.length()).get(s.length());
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = s.length();
        int n = p.length();
        List<List<Boolean>> dp = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            List<Boolean> inner = new ArrayList<>();
            if (i == 0 || (i > 0 && dp.get(i - 1).get(0) && p.charAt(i - 1) == '*')) inner.add(true);
            else inner.add(false);
            for (int j = 0; j < m; j++) {
                inner.add(false);
            }
            dp.add(inner);
        }
        
        return dp;

    }
}

Day 78, #41, First Missing Positive

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
----------------------------------------------------------------

# Pass 1, move every value to the position of its value

因为找的是第一个非0，所以把1存在0,2存在1

while里的条件是检测下一个位置是否已经匹配好，如果检查当前位置的话，会进入死循环，因为会有重复的数字如[1,1]

# Pass 2, find first location where the index doesn't match the value

reference  

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i = 0; i < n; i++) {
            int target = A[i];
            while (target > 0 && target <= n && A[target - 1] != target) {
                int temp = A[target - 1];
                A[target - 1] = target;
                A[i] = temp;
                target = A[i];
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (i + 1 != A[i]) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

Day 77, #31, Next Permutation

Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
--------------------------------------------------------------------------
Solution #1
Find the last peak number i, swap [i - 1] and the number that follows [i - 1] in ascending order, then reverse all numbers from peak to end

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size() == 0 || num.size() == 1) return;
        int peak = -1;
        int swapIndex = 0;
        
        for (int i = 0; i < num.size(); i++) {
            if (i + 1 < num.size() && num[i] < num[i + 1]) {
                peak = i + 1;
                swapIndex = peak;
            }else if (peak != -1) {
                if (num[i] > num[peak - 1]) {
                    swapIndex = i;
                }
            }    
        }
        
        if (peak == -1) {
            reverse(num.begin(),num.end());
        }else {
            int temp = num[swapIndex];
            num[swapIndex] = num[peak - 1];
            num[peak - 1] = temp;
            
            reverse(num.begin() + peak,num.end());
        }
    }
};

Java, updated on Aug-6th-2018
6 9 7 3 2 -> 7 2 3 6 9 可以看出规律

注意数字有重复的时候，比如2 3 1 3 3 -> 2 3 3 1 3. 所有第36行对比时要加等号

class Solution {
    public void nextPermutation(int[] nums) {
        int drop = getFirstDrop(nums);
        if (drop == -1) {
            reverseArray(nums, 0);
            return;
        }
        
        int nextInOrder = getNextInOrder(nums, drop);
        swap(nums, drop, nextInOrder);
        reverseArray(nums, drop + 1);
    }
    
    private void reverseArray(int[] nums, int index) {
        int right = nums.length - 1;
        
        while (index < right) {
            swap(nums, index, right);    
            index++;
            right--;
        }
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    private int getNextInOrder(int[] nums, int drop) {
        
        int index = drop + 1;
        int min = nums[index];
        
        for (int i = index; i < nums.length; i++) {
            if (min >= nums[i] && nums[i] > nums[drop]) { // 注意“>=”
                min = nums[i];
                index = i;
            }
        }
        
        return index;
    }
    
    private int getFirstDrop(int[] nums) {
        
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                return i;
            }
        }
        
        return -1;
    }
}