InterviewBit – MAXSPPROD

Source: MAXSPPROD

You are given an array A containing N integers. The special product of each i^th integer in this array is defined as the product of the following:

LeftSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (i>j). If multiple A[j]’s are present in multiple positions, the LeftSpecialValue is the maximum value of j.
RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] (j>i). If multiple A[j]s are present in multiple positions, the RightSpecialValue is the minimum value of j.

Write a program to find the maximum special product of any integer in the array.

Input: You will receive array of integers as argument to function.

Return: Maximum special product of any integer in the array modulo 1000000007.

Note: If j does not exist, the LeftSpecialValue and RightSpecialValue are considered to be 0.

Constraints 1 <= N <= 10^5 1 <= A[i] <= 10^9

解題：

這題個人覺得在題目並不難，主要是LSV跟RSV的定義相當tricky，在進行coding前須先將情況設想清楚：
- LSV: 對每個當前迴圈對目標陣列A迭代之索引值i，回傳符合A[j]>A[i] 且 j<i條件之索引值j，如有多個索引值j 符合該條件則回傳符合條件的最大值（與i值最相近者），如無相符之j值則回傳0；
- RSV: 對每個當前迴圈對目標陣列A迭代之索引值i，回傳符合A[j]>A[i] 且 j>i條件之索引值j，如有多個索引值j 符合該條件則回傳符合條件的最大值（與i值最相近者），如無相符之j值則回傳0；
- Example:
  [ 5, 9, 6, 8, 6, 4, 6, 9, 5, 4, 9]
  #LSV = [0, 0, 1, 1, 3, 4, 3, 0, 7, 8]
  #RSV = [1, 0, 3, 7, 7, 6, 7, 0, 0, 0]
  product = [0*1, 0*0, 1*3, 1*7, 3*7, 4*6, 3*7, 0*0, 7*0, 8*0]
因LSV及RSV作業機制基本上相同，只需要注意一個是從左至右另一個是從右至左進行迭代，以及針對索引值的取代機制如何運作即可。

Code:


class Solution:
    def _first_greater(self, A, prev=True):
        stack, ans = list(), [0] * len(A)
        it = range(len(A)) if prev else range(len(A)-1, -1, -1)
        for i in it:
            while stack and A[i] >= A[stack[-1]]:
                stack.pop()
            ans[i] = stack[-1] if stack else 0
            stack.append(i)
        return ans

    # @param A : list of integers
    # @return an integer
    def maxSpecialProduct(self, A):
        left = self._first_greater(A)
        right = self._first_greater(A, prev=False)
        maxx = -float('inf')
        for l, r in zip(left, right):
            maxx = max(l * r, maxx)
        return maxx % 1000000007

GitHub: GitHub

分享此文：

相關