程序员的算法趣题Q62: 日历中的最大矩形

时间：01-01来源：作者：点击数：38

1. 问题描述

2. 解题分析

2.1 每个月的日历的矩阵表示

在python中可以用calendar模块的monthcalendar()来实现。参见另一篇博客Python calendar模块的常用有趣用法。以下分别为两种方式打印的日历，第一条语句是将星期日设置为一周的第一天。

import calendar
calendar.setfirstweekday(calendar.SUNDAY)
calendar.prmonth(2014,4)
print(np.array(calendar.monthcalendar(2014,4)))

打印效果如下：

2.2 假日和调休公休日的处理

首先考虑假日的数据。

假日的数据在文件中是以以下形式存储的：

可以按行以字符串的形式读入，然后利用python datetime中模块将它们变换成datetime.datetime object并从中提取出年、月、日信息，然后再基于这个年月日信息将上一节得到的矩阵的对应元素置为0（表示非工作日）。

接下来考虑因调休变为工作日的公休日的数据。存储格式同上，以同样方式处理即可，只不过这次是将对应元素置为非0值（比如说置为1即可）。

在以下代码中用readfile()函数来从以上两个文件中读取数据，并提取日期信息，恢复出其中的年、月、日，然后存储在一个dict类型变量中，以(year, month)为key，value则是包含对应年月中的日期的列表。其中，设计到了利用datetime模块进行处理，关于datetime模块使用方法的简要介绍，参见博客：Python中日期时间处理：datetime包的实用示例

2.3 求最大矩形

2.3.1 暴力搜索

首先，求最大矩形问题当然可以用暴力搜索的方法来求解。

比如说，一个2*2的矩阵，其中以矩阵最左上角格子(0,0)为最左上角的矩形有多少个呢？恰好是4个。对于一般的情况n*m的矩阵，其中以矩阵最左上角格子(0,0)为最左上角的矩形总共有n*m个。扫描这n*m个矩形排除掉中间含有0元素的矩形（或者将其面积置0更简单），求剩下矩形的最大面积即得“以矩阵最左上角格子(0,0)为最左上角的矩形”的最大面积。接下来，同理可以求得以格子(0,1)、(0,2)、。。。、(1,0)、(1,1)、为最左上角的矩形的最大面积。再求这些最大值中的最大值即得当前矩阵中不含0元素的最大矩形面积。

这样暴力搜索的复杂度是多少呢？为简便起见，考虑原矩阵为正方形，大小为n*n

首先，对矩形最左上角的格子的扫描，n*n

其次，针对每个矩形最左上角格子候选，其对应的可能的矩形数取决于它的坐标。假定它的坐标为(i,j)，则可能的矩形数为(n-i)*(n-j)

这样，总的需要评估其面积的矩形个数为：

这种方案只能想一想作为基准参考，不能去实现。

2.3.2 滑动窗搜索

暴力搜索是以格子（考虑某个格子为所求矩形的左上角格子）为基点进行搜索。也可以从另一个角度考虑滑动窗方案，考虑以不同大小和形状的矩形框在日历矩形上滑动。因为是要求最大的矩形面积，所以扫描用的滑动矩形窗面积按从大到小的顺序安排，这样找到了第一个不包含0的滑动位置就找到了原题要求的最大矩形面积。

由于有可能多种形状的矩形框具有相同的面积，比如说4*2和2*4的矩形框的面积都为8。所以先构建一个字典，以面积为key，对应的可能的形状的列表作为value，代码如下：

# 2. Construct the dictionary for rectangulars area-shape pair
area_shape = dict()
for i in range(1,6):
    for j in range(1,8):
        if i*j not in area_shape:
            area_shape[i*j] = []
        area_shape[i*j].append((i,j))

有了以上准备工作后，针对某个月的处理流程如下所示：

注1：将holidays和extra-workdays对应元素的值重置时需要根据日期信息去确定它在矩阵中的对应位置。首先需要确定当月的第一天对应的weekday(星期几)，这样就能确定当月1日在矩阵中的位置，进而可以推得指定日期在矩阵中的位置。这个处理对应于以下代码（extra-workday的处理与此相同）：

        # Set holidays to 0
        if (y,m) in h:
            holidays = h[(y,m)]
            for hday in holidays:
                # Find the position of the current holiday in month calendar matrix
                i = (hday + fst_wkday - 1)//7
                j = (hday + fst_wkday - 1)%7
                c[i,j] = 0

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Nov 11 09:35:28 2021

@author: chenxy
"""

import sys
import time
from datetime import datetime
import math
# import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np
import calendar

#  Set SUNDAY to the first weekday
calendar.setfirstweekday(calendar.SUNDAY)
calendar.prmonth(2014,4)
print(np.array(calendar.monthcalendar(2014,4)))

def readfile(filename:str)->dict:
    '''
    Read holiday file and extra-workday file
    Parameters
    ----------
    filename : string        
    Returns
    -------
    A dictionary to store the data

    '''    
    print('Read {0} line by line, and store the holidays into a dictionary...'.format(filename))
    dat = dict()
    f=open(filename,'r')
    if f.mode == 'r':
        f_lines = f.readlines()
        for line in f_lines:
            # print(line,end='')
            date_object = datetime.strptime(line[:10], "%Y/%m/%d") # Strip the last '\n' in line
            # print("date_object ={}-{}-{}".format(date_object.year,date_object.month,date_object.day))        
            y,m,d = date_object.year,date_object.month,date_object.day
            if (y,m) not in dat:
                dat[(y,m)] = []
            dat[(y,m)].append(d)        
    f.close()
    return dat

# 1. Read the data file
h = readfile('q62-holiday.txt')
e = readfile('q62-extra-workday.txt')
    
# 2. Construct the dictionary for rectangulars area-shape pair
area_shape = dict()
for i in range(1,6):
    for j in range(1,8):
        if i*j not in area_shape:
            area_shape[i*j] = []
        area_shape[i*j].append((i,j))
        
# 3. loop over year/month to find the maximum rectangular of each month
max_area = dict()
for y in range(2014,2015):
    for m in range(4,7):
        # calendar.prmonth(y,m)
        c = np.array(calendar.monthcalendar(y,m))
        # Set the first and the last column to 0
        c[:,0] = 0
        c[:,6] = 0
        
        # print('The original month calendar:\n',c)
        # find the first weekday of the current month
        fst_wkday, num_days = calendar.monthrange(y, m)
        fst_wkday = (fst_wkday + 1)%7 # Because the SUNDAY is set to the first weekday
        
        # Set holidays to 0
        if (y,m) in h:
            holidays = h[(y,m)]
            for hday in holidays:
                # Find the position of the current holiday in month calendar matrix
                i = (hday + fst_wkday - 1)//7
                j = (hday + fst_wkday - 1)%7
                c[i,j] = 0

        # Set extra-workday to 100--any positive value is OK
        if (y,m) in e:
            extras = e[(y,m)]
            for eday in extras:
                # Find the position of the current extra workday in month calendar matrix
                i = (eday + fst_wkday - 1)//7
                j = (eday + fst_wkday - 1)%7
                c[i,j] = 100        
        # print('The month calendar after holidays and extra workdays setting:\n',c)
        # Search for the maximum rectangular only covering workday
        found = False
        for a in range(35,0,-1):
            # print(a)
            if a in area_shape:
                ij_list = area_shape[a]
                for (i,j) in ij_list:
                    for i0 in range(5-i+1):
                        for j0 in range(7-j+1):
                            rect = c[i0:i0+i,j0:j0+j]
                            # print(a,i,j,i0,j0, rect)
                            if np.all(rect):
                                max_area[(y,m)] = a
                                found = True
                                break
                        if found:
                            break
                    if found:
                        break
                if found:
                    break

print(max_area)

运行结果：{(2014, 4): 16, (2014, 5): 20, (2014, 6): 16}

以上代码没有完全回答题目所问的问题。原因是原书所附带数据并不完整，只有到2012/10/07为止的数据。所以我只参考题图补充了2014年4,5,6月的假日数据（这三个月没有公休日调休的情况），并测试了这三个月的最大矩形面积与题目描述中提示的值是否一致。但是，关于2014年6月的题目描述中提示的值其实是错的，很显然存在一个4*4的瓦完全工作日的矩形区域。