(nice!!!)(LeetCode 每日一题) 1717. 删除子字符串的最大得分 (贪心)

题目：1717. 删除子字符串的最大得分

思路：贪心，时间复杂度0(n)。

非a/b的字符，都可视为分隔符，将字符串s分割为多个只有ab的子串。然后在子串里，优先满足ab的情况(假设ab的分＞ba的分)，细节看注释。

C++版本：

class Solution {public: int maximumGain(string s, int x, int y) { // 优先处理分数大的情况， char a=\'a\',b=\'b\'; if(x<y){ swap(a,b); swap(x,y); } // sum是答案 // cta是当前子串里a字符的数量，ctb是当前子串里b字符的数量 int sum=0,cta=0,ctb=0; for(auto c:s){ // 优先判断ab的情况，所以遇到a字符时，cta++ if(c==a){ cta++; }else if(c==b){ //遇到b字符时，判断前面是否有a if(cta>0){  cta--;  sum+=x; }else{ //无a就记录b字符的数量，用于后面ba的情况  ctb++; } }else{ //遇到非a、b的字符，那么这一段子串处理就结束了 // ab的情况，前面都已经处理了，这里再处理ba的情况 sum+=y*min(cta,ctb); cta=0; ctb=0; } } // 处理边界情况 sum+=y*min(cta,ctb); return sum; }};

JAVA版本：

class Solution { public int maximumGain(String s, int x, int y) { char a=\'a\',b=\'b\'; if(x<y){ char t=a; a=b; b=t; int c=x; x=y; y=c; } int sum=0,cta=0,ctb=0; for(var c:s.toCharArray()){ if(c==a){ cta++; }else if(c==b){ if(cta>0){  cta--;  sum+=x; }else{  ctb++; } }else{ sum+=Math.min(cta,ctb)*y; cta=0; ctb=0; } } sum+=Math.min(cta,ctb)*y; return sum; }}

GO版本：

func maximumGain(s string, x int, y int) int { a,b:=\'a\',\'b\' if x<y { x,y=y,x a,b=b,a } sum,cta,ctb:=0,0,0 for _,c:=range s { if c==a { cta++ }else if c==b { if cta>0 { cta-- sum+=x }else { ctb++ } }else{ sum+=min(cta,ctb)*y cta=0 ctb=0 } } sum+=min(cta,ctb)*y return sum}