力扣刷题记录（14）LeetCode：763、56、738

目录

763.划分字母区间

56.合并区间

?738.单调递增的数字

总结

763.划分字母区间

这道题的关键点在于想到使用一个数组去存放每个字母在字符串中的最大索引。之后我们在遍历字符串的时候就知道应该在什么地方停止，想要得到最大分割次数，就应该在当前索引等于遍历过的字母在字符串中的最大索引时划分。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int last[26]={0};
        for(int i=0;i<s.size();i++)
        {
            last[s[i]-'a']=i;
        }
        vector<int> ans;
        int maxPositiion=0,sum=0;
        for(int i=0;i<s.size();i++)
        {
            //更新最远位置
            maxPositiion=max(maxPositiion,last[s[i]-'a']);
            sum++;
            if(i==maxPositiion)
            {
                //划分字母
                ans.push_back(sum);
                //最远位置归零
                maxPositiion=0;
                //字母数归零
                sum=0;
            } 
        }
        return ans;
    }
};

56.合并区间

?

如果刷了几篇文章的题目，那这道题就比较简单了。直接来个按照区间左值大小的方式排序。然后根据当前区间的左值和上一个区间的右值来判断两区间是否重叠，重叠就合并，不重叠就将上一个区间插入到ans中。

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)
    {
        if(a[0]==b[0])  return a[1]<b[1];
        else    return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        vector<vector<int>> ans;
        vector<int> v=intervals[0];
        for(int i=1;i<intervals.size();i++)
        {
            //如果当前区间的左值小于上一个区间的右值，两区间一定重合
            if(intervals[i][0]<=v[1])   v[1]=max(v[1],intervals[i][1]);
            //如果两区间不重合
            else
            {
                ans.push_back(v);
                v=intervals[i];
            }
        }
        //为什么加这一步？ 
        //1.如果只有一个元素，需要将这个元素放到ans中
        //2.因为要将最后一个区间放到ans中，for循环无法将最后一个区间放到ans中
        ans.push_back(v);
        return ans;
    }
};

?738.单调递增的数字

这道题可以先将其转换成字符串，方便判断每个数字的大小。对字符串从后向前遍历，如果遇到前一个值大于当前值的情况，我们就把前一个值减1，把当前值及当前值以后的值全部变成9。这样即可得到最大递增数字。

?

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //转成字符串
        string s=to_string(n);
        if(s.size()==1) return n;
        for(int i=s.size()-1;i>0;i--)
        {
            if(s[i-1]>s[i])
            {
                s[i-1]--;
                for(int j=i;j<s.size();j++)
                {
                    s[j]='9';
                }
            }
            
        }
        //转成整数
        return stoi(s);
    }
};

总结

贪心算法可以解决两类问题，一类是寻找最大值问题（跳跃游戏、买股票的最佳时机、最大子序列和等），另一类是区间问题（引爆气球、无重叠区间、合并区间等）。其实寻找最大值也是在一段区间中寻找，归根结底还是区间问题。只不过一些问题是在区间里面寻找最大值，一些问题是判断区间是否重叠。

?