PythonでKをインクリメントした後、同等の最長のサブリストを見つけるプログラム

numsとkという数のリストがあるとします。ここで、任意の1つの要素を1回インクリメントできる操作について考えてみます。最大でk回の操作を実行できる場合は、等しい要素を含む最長のサブリストを見つける必要があります。

したがって、入力がnums =[3、5、9、6、10、7] k =6のような場合、サブリスト[10、10を取得するために9を1回、6を4回インクリメントできるため、出力は3になります。 、10]。

これを解決するには、次の手順に従います-

• numsが空の場合、

  • 0を返す

• wMax：=numsと同じサイズの両端キュー。ペアを挿入します（nums [0]、0）

• i：=0、inc：=0

• 範囲1からnumのサイズまでのjについては、次のようにします

  • wMaxが空ではなく、wMax [0、1]

    • wMaxの左側の要素を削除する

  • pMax：=wMax [0、0]

  • wMaxが空ではなく、wMax <=nums [j]の最後の項目の最初の要素である場合、実行

    • wMaxから右の要素を削除する

  • wMaxの最後に（nums [j]、j）を挿入します

  • pMax

    • inc =inc +（j --i）*（wMax [0、0] --pMax）

  • それ以外の場合

    • inc：=inc + pMax-nums [j]

  • inc> kの場合、

    • inc：=inc --wMax [0、0] --nums [i]

    • wMaxが空ではなく、wMax [0、1] <=i、do

      • wMaxの左側の要素を削除する

    • wMax [0、0]

      • inc =inc-（nums [i] --wMax [0、0]）*（j --i）

    • i：=i + 1

• numsのサイズを返す-i

理解を深めるために、次の実装を見てみましょう-

例

from collections import deque
class Solution:
   def solve(self, nums, k):
      if not nums:
         return 0
      wMax = deque([(nums[0], 0)], maxlen=len(nums))
      i = 0
      inc = 0
      for j in range(1, len(nums)):
         while wMax and wMax[0][1] < i:
            wMax.popleft()
         pMax = wMax[0][0]

         while wMax and wMax[-1][0] <= nums[j]:
            wMax.pop()
         wMax.append((nums[j], j))
         if pMax < wMax[0][0]:
            inc += (j - i) * (wMax[0][0] - pMax)
         else:
            inc += pMax - nums[j]
         if inc > k:
            inc -= wMax[0][0] - nums[i]
            while wMax and wMax[0][1] <= i:
               wMax.popleft()
            if wMax[0][0] < nums[i]:
               inc -= (nums[i] - wMax[0][0]) * (j - i)
            i += 1
      return len(nums) - i
ob = Solution()
nums = [3, 5, 9, 6, 10, 7]
k = 6
print(ob.solve(nums, k))

入力

[3, 5, 9, 6, 10, 7], 6

出力

3