556. 下一个更大元素 III.Next Greater Element III.cpp [组合数学]

• **By Jalan**
• 题干
• 题解
• • 第一次
  • • 思路
    • 编写用时
    • 代码
    • • CPP
      • • 运行用时
• 结尾

要找到一个给定排列的数的下一个比他更大的排列
然后有一些琐碎的限制

要求:

1. 增大
2. 增大最少

对于这两个要求
要想使数值增大我们需要: 在低位找个大数和高位中的小数替换
那么如何使增大最小呢?
我们假设s[i]是最低的可以在比 i 更低的位找到某一位的值比i大的位置.
根据这个定义,i的右侧s[i+1,n]是降序的(s[i+1,n]每一位的低位都没有比他更大的值)
我们把s分为a+b,b就是s[i+1,n]的降序序列,a为s[0,i]的任意序列.
可知:如果替换位导致增加,那么只能是a中的小数和比这一位更低的位的大数替换导致
易得假如a中比i高的位发送替换导致增加,替换的增量总大于替换i位导致的增量.(最小值大于最大值)

所以如果我们要满足要求,我们应该替换i位和b中比i大的最小数.
然后把替换后的s[i+1,n]转为升序(最小排序)即可

我们顺序是:

1. 找到数值串中从低位到高位第一个比低一位大的位置i,找不到返回-1,找到执行2
2. 找到这i的低位中比这一位的数值大的最小的位j 一定存在
3. 替换i j的值
4. 将[i+1,size)升序排列 //倒转即可,因为替换后的序列其实也是降序.
5. 到这里,我们得到的结果是,n在能通过重排列增大的情况下,替换后增大的值最少的.如果超了,返回-1,不超,返回这个结果.

30分钟

// @before-stub-for-debug-begin
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
// @before-stub-for-debug-end



// @lc code=start
class Solution
{
public:
    int nextGreaterElement( int n )
    {
        string s    = to_string( n );
        int    size = s.size();
        if ( size <= 1 ) {
            return -1;
        }
        // 1. 找到数值串中从低位到高位第一个比低一位大的位置i,找不到返回-1,找到执行2
        int position = findDescendingSequenceAtTail( s );
        if ( position == -1 ) {
            return -1;
        }
        // 2. 找到这i的低位中比这一位的数值大的最小的位j 一定存在
        // 3. 替换i j的值
        swap( s[ position ], s[ findBiggerDigital( s.at( position ), s, position + 1, s.size() ) ] );
        // 4. 将[i+1,size)降序排列
        reverse( s.begin() + position + 1, s.end() );
        // 5. 到这里,我们得到的结果是,n在能通过重排列增大的情况下,替换后增大的值最少的.如果超了,返回-1,不超,返回这个结果.
        long long value = stoll( s );
        if ( value > 2147483647 )
            return -1;
        return static_cast< int >( value );
    }
    

    int findDescendingSequenceAtTail( const string& s )
    {
        int size = s.size();
        for ( int i = size - 1; i >= 1; i-- ) {
            if ( s[ i ] > s[ i - 1 ] ) {
                return i - 1;
            }
        }
        return -1;
    }
    
    int findBiggerDigital( int x, string& s, int begin, int end )
    {
        int minIndex = -1;
        for ( int i = end-1; i >=begin; i-- ) {
            if ( s[ i ] > x ) {
                if ( minIndex == -1 ) {
                    minIndex = i;
                } else if ( s[ i ] < s[ minIndex ] ) {
                    minIndex = i;
                }
            }
        }
        return minIndex;
    }
};
// @lc code=end

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀
@.@
也欢迎关注我的CSDN账号呀=]

                                        **开心code每一天**