发表于 2024.06.11

• 为了保证交换后的数字在小于原数字的要求下尽可能大，交换的位置应尽可能靠右。因此，我们从右往左扫描，找到第一个不满足升序的位置(即对于位置i有arr[i] > arr[i - 1])，然后在其右边找到最大的比它小的数（如果有重复值, 则交换最靠左的）arr[j]，交换这两个数即可。

  贪心可行性的证明:

  • 证明上述的待交换左侧位置i是最优的：如果存在一个更优的位置k，那么arr[k]必然在arr[i]右边，由于位置i右侧(不包括i)的数都是递增的，如果k作为交换的左侧位置，则交换后的数必然比原数更大，与要求矛盾。

  • 证明上述的待交换右侧位置j是最优的：如果位于i右侧存在一个更优的位置l，那么arr[l]必然大于arr[j]，而arr[j]是arr[i]右侧最大的比arr[i]小的数，因此交换arr[l]和arr[i]后，交换后的数必然比原数更大，与要求矛盾。

  class Solution:
      def countBattleships(self, board: List[List[str]]) -> int:
          ans = 0
  
          for i in range(len(board)):
              for j in range(len(board[i])):
                  if board[i][j] == 'X' and (i == 0 or board[i - 1][j] == '.') and (j == 0 or board[i][j - 1] == '.'):
                      ans += 1
          return ans

• LC 题目链接