2021-05-09周赛题解

题目一：人口最多的年份

1 2	https://leetcode-cn.com/problems/maximum-population-year/ ## 参考 https://leetcode-cn.com/problems/living-people-lcci/ 存活人数

方法一：暴力

观察数据范围，直接暴力法。

class Solution(object):
    def maximumPopulation(self, logs):
        res,year = 0,1950
        for i in range(1950,2051):
            temp = 0
            for per in logs:
                if i >= per[0] and i< per[1]: temp +=1
            if temp > res:
                res = temp
                year = i
        return year

方法二：查分数组

bore-died区间的计数加一，可以使用差分数组做区间修改。

时间复杂度 O(n)
空间复杂度 O(D)

func maximumPopulation(logs [][]int) int {
	arr := make([]int,101)
	for _,per := range logs {
		arr[per[0]-1950]+=1
		arr[per[1]-1950]-=1
	}
	res := arr[0]
	for i:=1;i<len(arr);i++ {
		arr[i] += arr[i-1]
		res = max(res,arr[i])
	}
	return res
}

题目二：下标对中距离最大值

1	https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values/

方法一：双指针

非递增数据，双指针进行求解

时间复杂度 O(n)
空间复杂度 O(1)

class Solution(object):
    def maxDistance(self, nums1, nums2):
        n,m = len(nums1),len(nums2)
        i,j = 0,0
        res = 0
        while i<n and j<m:
            if nums1[i] <= nums2[j]:
                while j<m and nums1[i]<=nums2[j]:
                    j+=1
                res = max(res,j-i-1)
            elif nums1[i] > nums2[j]:
                i+=1
        return res

题目三：子数组最小乘积的最大值

1
2
3

https://leetcode-cn.com/problems/maximum-subarray-min-product/
### 参考题目：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

方法一：单调队列+前缀和

子数组最小乘积：min(array[])*sum(array[])

数组中的数为正整数，子数组乘积的最大值分布在：以数组中每一个数字为最小值的最长数组中。

所有最长数组的max就是最大值。

数组中求以某个元素为最小值的最长子数组，就是找出数组中最左和最右第一个大于该元素的位置。

单调栈–>元素入栈时，已知左侧；出栈时候，已知右侧。如果出现相同，根据题意需要两次单调栈。

时间复杂度 O(n)
空间复杂度 O(n)

class Solution {
    int MOD = 1000000000 + 7;
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n+1];
        for(int i=1;i<=n;i++) {
            sum[i] = sum[i-1]+ nums[i-1];
        }

        Deque<Integer> stack = new LinkedList<>();
        int[] l = new int[n],r = new int[n];
        Arrays.fill(r,n-1);

        for(int i=0;i<n;i++){
            while (!stack.isEmpty() && nums[stack.peekLast()] > nums[i]) {
                Integer top = stack.pollLast();
                r[top] = i-1;
            }
            stack.offerLast(i);
        }

        for(int i=n-1;i>=0;i--){
            while (!stack.isEmpty() && nums[stack.peekLast()] > nums[i]) {
                Integer top = stack.pollLast();
                l[top] = i+1;
            }
            stack.offerLast(i);
        }

        Double res = 0D;
        for(int i=0;i<n;i++) {
            res = Math.max(res,nums[i]*(sum[r[i]+1]-sum[l[i]]));
        }
        return (int) (res%MOD);
    }
}

题目四：有向图的最大颜色值

1	https://leetcode-cn.com/problems/largest-color-value-in-a-directed-graph/

方法一：拓扑排序+DP

题目首先要求判断有向图是否有环，手段有：DFS，拓扑排序。如果拓扑序列<n，存在环。

对于有向无环图，假设一种颜色，可以按照拓扑顺序进行递归求解或者反拓扑顺序进行DP

在反拓扑序列进行DP时：DP[i] = max(DP[v] in edges[v])+ colors[i]==color ? 1:0

时间复杂度 O(26*n)
空间复杂度 O(n)

class Solution(object):
    def largestPathValue(self, colors, edges):
        mm,n = {},len(colors)
        inDegree = [0]*n
        for a,b in edges:
            inDegree[b]+=1
            if a not in edges: mm[a] = set()
            mm[a].add(b)
        q = Queue(maxsize=0)
        for i in range(n):
            if inDegree[i]==0: q.put(i)
        tp = []
        while len(q)>0:
            top = q.get()
            tp.append(top)
            for v in mm[top]:
                inDegree[v]-=1
                if inDegree[v]==0: tp.append(v)
        if len(tp)!=n : return -1

        res = 0
        for color in range(26):
            dp = [0]*n
            for i in range(n-1,-1,-1):
                u = tp[i]
                for v in mm[u]:
                    dp[u] = max(dp[u],dp[v])
                if (ord(colors[u])-ord('a')==color): dp[u]+=1
                res = max(res,dp[u])
        return res