LeetCode 每日一题 2026/8/24-2026/8/30-平芜编程栈

记录了初步解题思路以及本地实现代码；并不一定为最优也希望大家能一起探讨一起进步

- - 8/24 1872. 石子游戏 VIII
  - 8/25 3718. 缺失的最小倍数
  - 8/26 2904. 最短且字典序最小的美丽子字符串
  - 8/27 3720. 大于目标字符串的最小字典序排列
  - 8/28 3734. 大于目标字符串的最小字典序回文排列
  - 8/29 2948. 交换得到字典序最小的数组
  - 8/30 2091. 从数组中移除最大值和最小值

8/24 1872. 石子游戏 VIII

每次取最左边至少两枚石子，得分加上它们的和，再把这个和作为一枚新石子放回最左。
这等价于在原数组前缀和 s 上选一个下标 i，得分为 s[i]，剩余变成 [s[i], stones[i+1], …]。
双方轮流，当前玩家要最大化自己与对手的分数差。令 f[i] 表示还能选下标 >= i 时的最优分差。
只剩全部取走时 f[n-1] = s[n-1]；否则可跳过 i 得到 f[i+1]，或取走 s[i] 后对手拿 f[i+1]，即 f[i] = max(f[i+1], s[i] - f[i+1])。
Alice 第一步至少取两枚，从下标 1 开始，答案为 f[1]。从右往左滚动更新即可。

defstoneGameVIII(stones):""" :type stones: List[int] :rtype: int """n=len(stones)s=stones[:]foriinrange(1,n):s[i]+=s[i-1]f=s[n-1]foriinrange(n-2,0,-1):f=max(f,s[i]-f)returnf

8/25 3718. 缺失的最小倍数

依次便利k的倍数

defmissingMultiple(nums,k):""" :type nums: List[int] :type k: int :rtype: int """cur=k s=set(nums)whilecurins:cur+=kreturncur

8/26 2904. 最短且字典序最小的美丽子字符串

如果k>1 为了使最短必定收尾为1
滑动窗口找到k个1的子串比较长度和字典序

defshortestBeautifulSubstring(s,k):""" :type s: str :type k: int :rtype: str """ifk==1:return"1"if"1"inselse""n=len(s)left=0whileleft<nands[left]!="1":left+=1right=left+1count=1min_length=float('inf')min_substring=""whileright<n:ifs[right]=="1":count+=1ifcount==k:ifright-left+1<min_length:min_length=right-left+1min_substring=s[left:right+1]elifright-left+1==min_lengthands[left:right+1]<min_substring:min_substring=s[left:right+1]count-=1left+=1whileleft<nands[left]!="1":left+=1right+=1returnmin_substring

8/27 3720. 大于目标字符串的最小字典序排列

要找 s 的重排中严格大于 target 且字典序最小的串，不存在则返回空串。
字典序最小意味着尽量长地与 target 前缀相同，再在最早允许的“变大”位置上放最小的更大字母，剩余字母升序填完。
从左到右匹配 target：若当前还能用剩余字母配出 target[i] 则继续，同时记录还能换成更大字母的最右位置。
若没有任何位置能变大则无解；否则在该位置放入最小的更大字母，后面用剩余字母按 a-z 排好。

deflexGreaterPermutation(s,target):""" :type s: str :type target: str :rtype: str """n=len(s)cnt=[0]*26forchins:cnt[ord(ch)-97]+=1rem=cnt[:]last=-1fori,chinenumerate(target):t=ord(ch)-97forcinrange(t+1,26):ifrem[c]:last=ibreakifrem[t]==0:breakrem[t]-=1iflast<0:return""res=[]foriinrange(last):t=ord(target[i])-97res.append(target[i])cnt[t]-=1t=ord(target[last])-97forcinrange(t+1,26):ifcnt[c]:res.append(chr(c+97))cnt[c]-=1breakforcinrange(26):ifcnt[c]:res.append(chr(c+97)*cnt[c])return"".join(res)

8/28 3734. 大于目标字符串的最小字典序回文排列

s 能构成回文排列当且仅当奇数次字母至多一种，否则无解。
回文由左半段决定，奇数长度时中间字母固定为那个奇数次字母，左半每种字母最多用频次的一半。
要得到严格大于 target 的最小回文，应尽量让左半与 target 前缀相同。
先按 target 左半匹配，若整段都能配出，镜像后已大于 target 则直接返回。
否则从失配位起换成最小的更大字母，剩余按升序填满左半再镜像；换不了就回退前一位。
全部回退仍无解则返回空串。

deflexPalindromicPermutation(s,target):""" :type s: str :type target: str :rtype: str """n=len(s)cnt=[0]*26forchins:cnt[ord(ch)-97]+=1mid=-1fori,cinenumerate(cnt):ifc%2:ifmid>=0:return""mid=i cnt[i]//=2half=n//2defmake(left):ifn%2:returnleft+chr(mid+97)+left[::-1]returnleft+left[::-1]left=[]pos=0whilepos<half:t=ord(target[pos])-97ifcnt[t]==0:breakleft.append(target[pos])cnt[t]-=1pos+=1ifpos==half:cand=make("".join(left))ifcand>target:returncandwhileTrue:ifpos<half:t=ord(target[pos])-97forcinrange(t+1,26):ifcnt[c]:cnt[c]-=1rest=[chr(c+97)]foriinrange(26):rest.append(chr(i+97)*cnt[i])returnmake("".join(left)+"".join(rest))ifpos==0:return""pos-=1cnt[ord(left.pop())-97]+=1

8/29 2948. 交换得到字典序最小的数组

只要 |a-b|<=limit 就可以交换，经若干次后，按值排序后相邻差都不超过 limit 的数会落在同一连通块，块内可任意重排。
把 (值, 下标) 按值排序，相邻差 > limit 处切开，每个连通块内把排序后的值依次填回排序后的原下标，整体就是字典序最小数组。

deflexicographicallySmallestArray(nums,limit):""" :type nums: List[int] :type limit: int :rtype: List[int] """n=len(nums)arr=sorted(zip(nums,range(n)))ans=[0]*n i=0whilei<n:j=i+1whilej<nandarr[j][0]-arr[j-1][0]<=limit:j+=1idx=sorted(kfor_,kinarr[i:j])fork,(x,_)inzip(idx,arr[i:j]):ans[k]=x i=jreturnans

8/30 2091. 从数组中移除最大值和最小值

遍历一遍数据找到最大最小值位置
去除一共三种情况
都从左边取出
都从右边取出
分别从左右取出

defminimumDeletions(nums):""" :type nums: List[int] :rtype: int """maxv,minv=float('-inf'),float('inf')maxloc,minloc=-1,-1fori,numinenumerate(nums):ifnum>maxv:maxv=num maxloc=iifnum<minv:minv=num minloc=i n=len(nums)left=min(maxloc,minloc)right=max(maxloc,minloc)print(n,left,right)ans=min(right+1,n-left,left+1+n-right)returnans