1.最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
思路：利用辅助栈

class MinStack {
    stack<int> s1;   
    stack<int> sMin;//这两个在public之前写
public:
    /** initialize your data structure here. */

    MinStack() {
        sMin.push(INT_MAX);//先放入一个无穷大       
    }

    void push(int x) {
        s1.push(x);
        if(!sMin.empty()&&s1.top()<sMin.top())
        {
            sMin.push(s1.top());
        }
        else
        {
            sMin.push(sMin.top());
        }      
    }

    void pop() {
        s1.pop();
        sMin.pop();

    }

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

    int getMin() {
        return sMin.top();       
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2.丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路：因为丑数只包含质因子2，3和5，因此后面的质因子一定是前面的质因子乘以这三个数产生的，所以我们设置三个位置p2，p3和p5，由前面的丑数来推后面的丑数。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
       if(index<=0) return 0;
        vector<int> res;
        int num=1;
        res.push_back(num);//先放入第一个丑数
        int p2=0,p3=0,p5=0;
        while(res.size()<index)
        {
            int num=min(res[p2]*2,min(res[p3]*3,res[p5]*5));//找最小的
            res.push_back(num);
            while(res[p2]*2<=num)
                p2++;
            while(res[p3]*3<=num)
                p3++;
            while(res[p5]*5<=num)
                p5++;//更新区间
        }
        return res.back();       
    }
};

3.第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.length()<=0) return -1;
        //利用数组实现哈希表，key是下标，value是数组的值
        int alpha[256]={0};
        for(int i=0;str[i]!='\0';i++)
        {
            alpha[str[i]]++;//记录次数
        }
        for(int i=0;str[i]!='\0';i++)
        {
            if(alpha[str[i]]==1)
                return i;//返回第一个
        }
        return -1;
    }
};

4.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007
思路：基于归并排序的统计

class Solution {
public:
    int InversePairs(vector<int> data) {
       int length=data.size();
        if(length<=0)
            return 0;
       vector<int> copy;
       for(int i=0;i<length;i++)
           copy.push_back(data[i]);
       long long count=InversePairsCore(data,copy,0,length-1);
    //假设是7564，先分为75,64，再分为7,5,6,4，合并成57,46产生两个逆序对，然后合并成4567，产生三个逆序对
       return count%1000000007;
    }
    long long InversePairsCore(vector<int> &data,vector<int> &copy,int start,int end)
    {
       if(start==end)
          {
            copy[start]=data[start];
            return 0;
          }
       int length=(end-start)/2;//二分
       long long left=InversePairsCore(copy,data,start,start+length);//57
       long long right=InversePairsCore(copy,data,start+length+1,end); //46

       int i=start+length;
       int j=end;
       int indexcopy=end;
       long long count=0;
       while(i>=start&&j>=start+length+1)//从后往前找
          {
             if(data[i]>data[j])
                {
                  copy[indexcopy--]=data[i--];
                  count=count+j-start-length;          //count=count+j-(start+length+1)+1;
                }//i大于j前面所有的数，7大于6，那么就大于4和6
             else
                {
                  copy[indexcopy--]=data[j--];//5小于6，放入6，没有逆序对
                }          
          }
       for(;i>=start;i--)
           copy[indexcopy--]=data[i];
       for(;j>=start+length+1;j--)
           copy[indexcopy--]=data[j];       
       return left+right+count;
    }
};