요소를 오른쪽에서 가장 큰 요소로 바꾸기

2170 단어 theabbieleetcodedsa
배열arr이 주어지면 해당 배열의 모든 요소를 ​​오른쪽에 있는 요소 중 가장 큰 요소로 바꾸고 마지막 요소를 -1로 바꿉니다.

그런 다음 배열을 반환하십시오.

예 1:

입력: arr = [17,18,5,4,6,1]
출력: [18,6,6,6,1,-1]
설명:
  • 인덱스 0 --> 인덱스 0 오른쪽에 있는 가장 큰 요소는 인덱스 1입니다(18).
  • 인덱스 1 --> 인덱스 1 오른쪽에 있는 가장 큰 요소는 인덱스 4입니다(6).
  • 인덱스 2 --> 인덱스 2 오른쪽에 있는 가장 큰 요소는 인덱스 4입니다(6).
  • 인덱스 3 --> 인덱스 3 오른쪽에 있는 가장 큰 요소는 인덱스 4(6)입니다.
  • 인덱스 4 --> 인덱스 4 오른쪽에 있는 가장 큰 요소는 인덱스 5(1)입니다.
  • 인덱스 5 --> 인덱스 5 오른쪽에 요소가 없으므로 -1을 넣습니다.

  • 예 2:

    입력: arr = [400]
    출력: [-1]
    설명: 인덱스 0 오른쪽에 요소가 없습니다.

    제약:
  • 1 <= arr.length <= 104
  • 1 <= arr[i] <= 105

  • 해결책:

    class Solution:
    #     def makeSeg(self, arr, i, j):
    #         seg = self.seg
    #         if (i, j) in seg:
    #             return seg[(i, j)]
    #         if i == j:
    #             seg[(i, j)] = arr[i]
    #             return arr[i]
    #         mid = (i + j) // 2
    #         curr = max(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j))
    #         seg[(i, j)] = curr
    #         return curr
    
    #     def getMax(self, arr, i, j, ni, nj):
    #         seg = self.seg
    #         if ni >= i and nj <= j:
    #             return seg[(ni, nj)]
    #         if (ni < i and nj < i) or (ni > j and nj > j):
    #             return float('-inf')
    #         mid = (ni + nj) // 2
    #         return max(self.getMax(arr, i, j, ni, mid), self.getMax(arr, i, j, mid + 1, nj))
    
    #     def replaceElements(self, arr: List[int]) -> List[int]:
    #         n = len(arr)
    #         self.seg = {}
    #         self.makeSeg(arr, 0, n - 1)
    #         for i in range(n):
    #             if i < n - 1:
    #                 arr[i] = self.getMax(arr, i + 1, n, 0, n - 1)
    #             else:
    #                 arr[i] = -1
    #         return arr
    
        def replaceElements(self, arr: List[int]) -> List[int]:
            n = len(arr)
            op = [-1] * n
            currMax = float('-inf')
            for i in range(n - 1, 0, -1):
                currMax = max(currMax, arr[i])
                op[i - 1] = currMax
            return op
    

    좋은 웹페이지 즐겨찾기